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.
sequences = [[1,2],[1,3]], there are two shortest supersequences, [1,2,3] and [1,3,2].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 <= 104nums is 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] <= nsequences are unique.sequences[i] is a subsequence of nums.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.
We can first traverse each subsequence seq. For each pair of adjacent elements a and b, we establish a directed edge a \to b. At the same time, we count the in-degree of each node, and finally add all nodes with an in-degree of 0 to the queue.
When the number of nodes in the queue is equal to 1, we take out the head node i, remove i from the graph, and decrease the in-degree of all adjacent nodes of i by 1. If the in-degree of the adjacent nodes becomes 0 after decreasing, add these nodes to the queue. Repeat the above operation until the length of the queue is not 1. At this point, check whether the queue is empty. If it is not empty, it means there are multiple shortest supersequences, return false; if it is empty, it means there is only one shortest supersequence, return true.
The time complexity is O(n + m), and the space complexity is O(n + m). Where n and m are the number of nodes and edges, respectively.
Python
Java
C++
Go
TypeScript
| 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 |
LeetCode 444. Sequence Reconstruction • Happy Coding • 4,743 views views
Watch 7 more video solutions →Practice Sequence Reconstruction with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor