Sequence Reconstruction medium
Description
You are given an integer array nums of length n where nums is a permutation of the integers in the range [1, n]. You are also given a 2D integer array sequences where sequences[i] is a subsequence of nums.
Check if nums is the shortest possible and the only supersequence of all the subsequences in sequences. The shortest supersequence is a sequence of the minimum length that has every subsequence in sequences as a subsequence.
Return true if nums is the unique shortest supersequence for sequences, false otherwise.
Examples
> Case 1:
nums = [1, 2, 3], sequences = [[1, 2], [1, 3]]
Output: false
Explanation: both [1, 2, 3] and [1, 3, 2] are valid supersequences of the constraints.
> Case 2:
nums = [1, 2, 3], sequences = [[1, 2]]
Output: false
> Case 3:
nums = [1, 2, 3], sequences = [[1, 2], [1, 3], [2, 3]]
Output: trueConstraints
n == nums.length1 <= n <= 10^4numsis a permutation of all the integers in the range[1, n].
State design
Two questions to answer:
- Is the topo order of the implied DAG equal to
nums? (Does it agree?) - Is the topo order unique? (No other valid order exists?)
The “unique” check is the trick: a topo order is unique iff at every step of Kahn’s, the queue contains exactly one node. If the queue ever has 2+ zero-indegree nodes simultaneously, multiple valid orderings exist.
Code
The “queue size == 1” uniqueness check is the entire insight. A topo order is unique iff there’s no ambiguity at any step about which node to emit next. Kahn’s makes that explicit: if multiple eligible nodes are in the queue at once, ANY of them could be emitted, and a different choice would produce a different valid order. So we check size before each emission.
Analysis
- Time:
O(V + E)whereEis the total length of all sequences. - Space:
O(V + E).
Same skin
- Alien Dictionary — different framing (characters from word ordering), same algorithmic core.
- Course Schedule II — output the order (without uniqueness check).
- Verifying a Topological Order — given a proposed order, check it’s valid (single pass, no topo sort).
- Unique Number of Occurrences — different problem, related “uniqueness” feel.