444. Sequence Reconstruction

How to solve Sequence Reconstruction (LeetCode 444): the approach in brief

The problem

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.

Pattern

Sequence Reconstruction is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.

Approach outline

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?

Complexity

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

Asked at

Sequence Reconstruction has been reported in interviews at Google.