Skip to main content
Talentd

Sequence Reconstruction - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGraphTopological Sort11 min readAsked at: Amazon, Google
Practice this problem

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.length
  • 1 <= n <= 104
  • nums is a permutation of all the integers in the range [1, n].
  • 1 <= sequences.length <= 104
  • 1 <= sequences[i].length <= 104
  • 1 <= sum(sequences[i].length) <= 105
  • 1 <= sequences[i][j] <= n
  • All the arrays of sequences are unique.
  • sequences[i] is a subsequence of nums.

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph + Kahn's Topological SortO(V + E)O(V + E)Best general solution when verifying unique ordering from subsequences
DFS-Based Topological OrderingO(V + E)O(V + E)Useful when DFS graph traversal is already implemented or recursion-based ordering is preferred
Edge Validation Using Consecutive PairsO(V + E)O(V)When you want a lightweight check ensuring every adjacent pair in org appears in constraints

Video Solution

LeetCode 444. Sequence Reconstruction • Happy Coding • 4,885 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Sequence Reconstruction easy or hard?
Sequence Reconstruction is generally classified as a medium difficulty problem. The coding portion is manageable once you recognize it as a topological sorting problem, but the uniqueness constraint and graph construction make it trickier than standard ordering problems.
Sequence Reconstruction Python/Java solution
Most implementations build a graph using a dictionary or map, track indegree counts, and run a BFS queue for topological sorting. The same logic works across Python, Java, C++, Go, and TypeScript with minor syntax differences. The critical step is ensuring the queue size is always exactly one.
How to solve Sequence Reconstruction in O(n)?
Model the subsequences as a directed graph and apply Kahn’s topological sort. Track indegrees and process nodes with indegree 0. If at any step more than one node is available, multiple valid orders exist and the reconstruction is not unique. The algorithm processes each node and edge once, giving O(V + E) complexity.
What is the best approach for Sequence Reconstruction?
The most reliable approach uses graph construction followed by Kahn’s topological sort. Nodes represent numbers and edges represent ordering constraints from subsequences. During BFS processing, the queue must always contain exactly one node to guarantee uniqueness. This runs in O(V + E) time and O(V + E) space.
Is Sequence Reconstruction asked at Google/Amazon/Meta?
Sequence Reconstruction is a classic graph ordering problem related to topological sorting and dependency resolution. Variants of this problem appear in interviews at large tech companies such as Google, Amazon, and Meta because it tests graph modeling and reasoning about unique orderings.
What data structure is used in Sequence Reconstruction?
The solution typically uses an adjacency list to represent the directed graph, a hash map or array to track indegrees, and a queue for BFS processing during Kahn’s algorithm. These structures allow efficient updates while enforcing ordering constraints.
What is the time complexity of Sequence Reconstruction?
The optimal solution runs in O(V + E) time where V is the number of unique elements and E is the number of ordering relations derived from subsequences. Building the graph and performing topological sorting both scale linearly with the number of nodes and edges.

Ready to solve this problem?

Practice Sequence Reconstruction with our built-in code editor and test cases.

Practice on FleetCode
Previous

Course Schedule II