Sequence Reconstruction
Explanation & Solution
Description
Given a sequence org of integers from 1 to n and a list of subsequences called seqs, determine whether org is the only shortest supersequence of all the given subsequences.
A supersequence is a sequence that contains each of the given subsequences as a subsequence. The shortest supersequence is one with the minimum possible length.
Return true if org is the only shortest supersequence of seqs, or false otherwise.
Examples
Example 1
Input: org = [1,2,3], seqs = [[1,2],[1,3]]
Output: false
Explanation: [1,2,3] is not the only shortest supersequence. [1,3,2] is also a valid shortest supersequence. Since the ordering is not unique, we return false.
Example 2
Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Output: true
Explanation: [1,2,3] is the only shortest supersequence of the given subsequences. Every pair of consecutive elements in org is constrained by the subsequences, making it the unique topological ordering.
Example 3
Input: org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Output: true
Explanation: The subsequences fully constrain the ordering so that [4,1,5,2,6,3] is the only valid shortest supersequence.
Constraints
- 1 <= n <= 10^4
- org is a permutation of integers from 1 to n
- 1 <= seqs.length <= 10^4
- 1 <= seqs[i].length <= 10^4
- 1 <= seqs[i][j] <= n
Approach
Topological Sort pattern
1. Build the Directed Graph
- For each subsequence, create directed edges between every pair of consecutive elements.
- Track the in-degree of every node and build an adjacency list.
- If any value is out of range or not all nodes 1..n appear in seqs, return false.
2. Perform Topological Sort with Uniqueness Check
- Initialize a queue with all nodes that have in-degree 0.
- At each step, check that the queue contains exactly one element. If there are ever two or more nodes with in-degree 0 simultaneously, there are multiple valid orderings, so the answer is false.
3. Validate Against org
- As we process each node from the queue, verify it matches the corresponding position in org.
- If it doesn't match, the given org is not a valid topological ordering of the constraints, so return false.
4. Confirm All Nodes Processed
- After the loop, check that we processed exactly n nodes.
- If yes, org is the unique shortest supersequence.
Key Insight
- A unique topological ordering exists if and only if at every step during BFS-based topological sort, there is exactly one node with in-degree 0. This means there's no ambiguity in the ordering — each element's position is fully determined by the constraints from the subsequences.