Sequence Reconstruction - Video Solutions
LeetCode 444. Sequence Reconstruction
Sequence Reconstruction - Video Solution
Watch 8 video solutions for Sequence Reconstruction, a medium level problem involving Array, Graph, Topological Sort. This walkthrough by Happy Coding has 4,885 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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. The shortest supersequence is a sequence with the shortest length and has all sequences[i] as subsequences. There could be multiple valid supersequences for the given array sequences.
- For example, for
sequences = [[1,2],[1,3]], there are two shortest supersequences,[1,2,3]and[1,3,2]. - While for
sequences = [[1,2],[1,3],[1,2,3]], the only shortest supersequence possible is[1,2,3].[1,2,3,4]is a possible supersequence but not the shortest.
Return true if nums is the only shortest supersequence for sequences, or false otherwise.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,2,3], sequences = [[1,2],[1,3]] Output: false Explanation: There are two possible supersequences: [1,2,3] and [1,3,2]. The sequence [1,2] is a subsequence of both: [1,2,3] and [1,3,2]. The sequence [1,3] is a subsequence of both: [1,2,3] and [1,3,2]. Since nums is not the only shortest supersequence, we return false.
Example 2:
Input: nums = [1,2,3], sequences = [[1,2]] Output: false Explanation: The shortest possible supersequence is [1,2]. The sequence [1,2] is a subsequence of it: [1,2]. Since nums is not the shortest supersequence, we return false.
Example 3:
Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]] Output: true Explanation: The shortest possible supersequence is [1,2,3]. The sequence [1,2] is a subsequence of it: [1,2,3]. The sequence [1,3] is a subsequence of it: [1,2,3]. The sequence [2,3] is a subsequence of it: [1,2,3]. Since nums is the only shortest supersequence, we return true.
Constraints:
n == nums.length1 <= n <= 104numsis a permutation of all the integers in the range[1, n].1 <= sequences.length <= 1041 <= sequences[i].length <= 1041 <= sum(sequences[i].length) <= 1051 <= sequences[i][j] <= n- All the arrays of
sequencesare unique. sequences[i]is a subsequence ofnums.
Approach Overview
Problem Overview: You’re given the original sequence org and a list of subsequences seqs. The task is to verify whether org is the only sequence that can be reconstructed while respecting the relative ordering inside every subsequence.
The key challenge is uniqueness. Multiple valid topological orders would mean the reconstruction is not uniquely determined. This turns the problem into a graph ordering check using Graph traversal and Topological Sort.
Approach 1: Graph Construction + Kahn's Topological Sort (O(V + E) time, O(V + E) space)
Treat every number as a node and every adjacent pair in seqs as a directed edge. Build an adjacency list and an indegree map while iterating through all subsequences. After the graph is built, run Kahn’s BFS-based topological sort. Maintain a queue of nodes with indegree 0.
The uniqueness constraint comes from the queue size. If the queue ever contains more than one node, multiple valid orders exist, so reconstruction is not unique. At each step, pop the only available node and verify it matches the corresponding element in org. Then decrement indegrees of its neighbors. If the entire sequence matches and all nodes are processed, org is uniquely reconstructible.
This approach works because topological sorting enforces ordering constraints from all subsequences simultaneously. Checking that the queue size is always exactly one guarantees only a single valid ordering exists.
Approach 2: DFS-Based Topological Ordering Validation (O(V + E) time, O(V + E) space)
Another method builds the same directed graph but performs a DFS-based topological ordering. Each node is visited recursively while tracking visited states (unvisited, visiting, visited). After generating a topological order, compare it with org.
However, DFS alone does not easily enforce uniqueness during traversal. Additional checks are required to confirm that every consecutive pair in org is directly constrained by edges in the graph. Because of this extra logic, the implementation becomes more complex than the BFS approach.
Both approaches rely heavily on graph modeling rather than raw Array manipulation. The subsequences simply define edges between elements.
Recommended for interviews: Kahn’s algorithm with a uniqueness check is the expected solution. It clearly demonstrates understanding of graph construction, indegree tracking, and topological ordering. Explaining why the queue must contain exactly one element at each step shows strong reasoning about ordering constraints.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph + Kahn's Topological Sort | O(V + E) | O(V + E) | Best general solution when verifying unique ordering from subsequences |
| DFS-Based Topological Ordering | O(V + E) | O(V + E) | Useful when DFS graph traversal is already implemented or recursion-based ordering is preferred |
| Edge Validation Using Consecutive Pairs | O(V + E) | O(V) | When you want a lightweight check ensuring every adjacent pair in org appears in constraints |