444. Sequence Reconstruction

Sequence Reconstruction (LeetCode 444) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

How to solve Sequence Reconstruction

Sequence Reconstruction is a Topological Sort problem, part of Graph Traversal Patterns (DFS & BFS). Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.

Work towards the solution in these steps:

1. Consider representing the problem as a graph where each unique integer is a node and the ordering in sequences represents directed edges.
2. Think about how you can use topological sorting to determine if the sequences in seqs can reconstruct the original sequence org.
3. Recall that Kahn's Algorithm for topological sorting uses a queue and processes nodes with zero in-degree; how can this help verify uniqueness?

The reference solution runs in O(n * s) time and O(n) space.

The Sequence Reconstruction solution and editorial walks through the full approach with reference code.

Problem statement

You are given an integer array org of length n, which is a permutation of the integers from 1 to n. You are also given a list of sequences seqs, where each seqs[i] is a subsequence of org.

A sequence can be uniquely reconstructed from seqs if it is the shortest common supersequence of all sequences in seqs (i.e., it contains all sequences in seqs as subsequences) and there is no other sequence that satisfies this property.

Return true if org can be uniquely reconstructed from seqs. Otherwise, return false.

Constraints: - 1 <= n <= 10^4 - org is a permutation of the integers from 1 to n - All elements in seqs are integers in the range [1, n] - The length of each seqs[i] is at least 1 and fits in a 32-bit signed integer

Examples

Topics and companies

Topics: Array, Graph, Topological Sort.

Reported in interviews at Google.

How to practise Sequence Reconstruction on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * s) time and O(n) space.

Open Sequence Reconstruction in the code editor, or read the Sequence Reconstruction editorial for a worked solution with its approach and complexity analysis.

Where Sequence Reconstruction sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph BFS - Topological Sort (Kahn's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Sequence Reconstruction

Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Alien Dictionary — Hard, same subpattern
• Build a Matrix With Conditions — Hard, same subpattern
• Course Schedule IV — Medium, same subpattern
• Find All Possible Recipes from Given Supplies — Medium, same subpattern
• Largest Color Value in a Directed Graph — Hard, same subpattern
• Minimum Height Trees — Medium, same subpattern

Sequence Reconstruction FAQ