LeetCode 444: Sequence Reconstruction

Problem Restatement

We are given:

The array nums is a permutation of integers from 1 to n.

Each sequence in sequences is a subsequence of nums.

We need to check whether nums is the only shortest supersequence that contains every sequence in sequences as a subsequence.

A supersequence means it contains another sequence in the same relative order.

For example:

nums = [1, 2, 3]
sequences = [[1, 2], [1, 3]]

Both of these are valid shortest supersequences:

[1, 2, 3]
[1, 3, 2]

So nums is not uniquely determined.

The answer is:

False

The official problem asks whether nums is the shortest possible and only supersequence for sequences. A sequence is valid when every sequences[i] is its subsequence. (leetcode.com, doocs.org)

Input and Output

Example function shape:

def sequenceReconstruction(nums: list[int], sequences: list[list[int]]) -> bool:
    ...

Examples

Example 1:

nums = [1, 2, 3]
sequences = [[1, 2], [1, 3]]

Constraints:

1 before 2
1 before 3

After placing 1, both 2 and 3 are possible.

So there are two valid shortest supersequences:

[1, 2, 3]
[1, 3, 2]

Answer:

False

Example 2:

nums = [1, 2, 3]
sequences = [[1, 2]]

Only the order 1 before 2 is known.

The shortest supersequence can be:

[1, 2]

So nums = [1, 2, 3] is not the shortest possible supersequence.

Answer:

False

Example 3:

nums = [1, 2, 3]
sequences = [[1, 2], [1, 3], [2, 3]]

Constraints:

1 before 2
1 before 3
2 before 3

These force exactly:

[1, 2, 3]

Answer:

True

First Thought: Check Adjacent Pairs

A useful observation is that if nums is uniquely reconstructed, then every adjacent pair in nums must be forced by the constraints.

For example, for:

nums = [1, 2, 3]

we need evidence that:

1 before 2
2 before 3

If 2 before 3 is missing, then 2 and 3 may be swappable.

This gives a compact solution for some versions of the problem.

However, the most general way to express the logic is topological sorting. It also explains uniqueness clearly.

Key Insight

Each adjacent pair in a sequence gives an ordering constraint.

For example:

[5, 2, 6, 3]

means:

5 -> 2
2 -> 6
6 -> 3

So we can build a directed graph.

Each number is a node.

Each constraint a before b becomes a directed edge:

a -> b

Now the problem becomes:

Does this graph have exactly one topological ordering, and is that ordering equal to nums?

A topological order is unique only when, at every step, there is exactly one node with indegree 0.

If there are two or more choices, then multiple valid orders exist.

Algorithm

Build a graph with nodes 1 to n.

For every sequence:

1. For every adjacent pair (a, b), add edge a -> b.
2. Increase indegree of b only if this edge was not already added.

Then run Kahn’s topological sort.

Initialize a queue with all nodes whose indegree is 0.

Process nodes one by one.

At each step:

1. If the queue size is not exactly 1, return False.
2. Pop the only available node.
3. It must equal nums[index]; otherwise return False.
4. Decrease indegree of its neighbors.
5. Push neighbors whose indegree becomes 0.

At the end, return whether we processed all n nodes.

Correctness

Each subsequence gives relative-order constraints. Adding an edge a -> b for each adjacent pair means any valid supersequence must place a before b.

A topological ordering of this graph is exactly an ordering that satisfies all these constraints.

Kahn’s algorithm repeatedly chooses nodes with indegree 0. Such nodes have no remaining prerequisites, so they may legally appear next.

If the queue has more than one node, then there is more than one legal choice for the next position. Therefore, the reconstruction is not unique.

If the queue is empty before all nodes are processed, then the constraints contain a cycle or cannot form a complete valid order.

If the queue has exactly one node at every step, then the topological order is forced. The algorithm also checks that each forced node equals the corresponding element of nums.

Therefore, the algorithm returns True exactly when the constraints force one unique topological order and that order is nums.

Complexity

Here, m is the total number of adjacent-pair constraints across all sequences.

Implementation

from collections import deque

class Solution:
    def sequenceReconstruction(
        self,
        nums: list[int],
        sequences: list[list[int]],
    ) -> bool:
        n = len(nums)

        graph = [set() for _ in range(n + 1)]
        indegree = [0] * (n + 1)

        for seq in sequences:
            for i in range(len(seq) - 1):
                a = seq[i]
                b = seq[i + 1]

                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1

        queue = deque()

        for value in range(1, n + 1):
            if indegree[value] == 0:
                queue.append(value)

        index = 0

        while queue:
            if len(queue) != 1:
                return False

            node = queue.popleft()

            if index == n or nums[index] != node:
                return False

            index += 1

            for nei in graph[node]:
                indegree[nei] -= 1

                if indegree[nei] == 0:
                    queue.append(nei)

        return index == n

Code Explanation

We create a graph with one set per value:

graph = [set() for _ in range(n + 1)]

The set prevents duplicate edges from increasing indegree more than once.

The indegree array stores how many prerequisites each number has:

indegree = [0] * (n + 1)

For each adjacent pair in each sequence:

a = seq[i]
b = seq[i + 1]

we add the ordering constraint:

a -> b

Only new edges should increase indegree:

if b not in graph[a]:

Then we collect all nodes with no prerequisites:

if indegree[value] == 0:
    queue.append(value)

During topological sorting, uniqueness requires:

if len(queue) != 1:
    return False

Then the only possible node must match nums[index]:

if index == n or nums[index] != node:
    return False

After removing a node, we reduce indegrees of its neighbors:

indegree[nei] -= 1

When a neighbor becomes available, we push it:

if indegree[nei] == 0:
    queue.append(nei)

Finally:

return index == n

confirms that all nodes were processed.

Testing

def run_tests():
    s = Solution()

    assert s.sequenceReconstruction(
        [1, 2, 3],
        [[1, 2], [1, 3]],
    ) is False

    assert s.sequenceReconstruction(
        [1, 2, 3],
        [[1, 2]],
    ) is False

    assert s.sequenceReconstruction(
        [1, 2, 3],
        [[1, 2], [1, 3], [2, 3]],
    ) is True

    assert s.sequenceReconstruction(
        [4, 1, 5, 2, 6, 3],
        [[5, 2, 6, 3], [4, 1, 5, 2]],
    ) is True

    assert s.sequenceReconstruction(
        [1],
        [[1]],
    ) is True

    assert s.sequenceReconstruction(
        [1, 2, 3],
        [[1, 2], [2, 3], [1, 2]],
    ) is True

    print("all tests passed")

run_tests()

Test meaning: