# LeetCode 444: Sequence Reconstruction

## Problem Restatement

We are given:

| Name | Meaning |
|---|---|
| `nums` | The target sequence |
| `sequences` | A list of subsequences |

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:

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

Both of these are valid shortest supersequences:

```python
[1, 2, 3]
[1, 3, 2]
```

So `nums` is not uniquely determined.

The answer is:

```python
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](https://leetcode.com/problems/sequence-reconstruction/), [doocs.org](https://github.com/doocs/leetcode/blob/main/solution/0400-0499/0444.Sequence%20Reconstruction/README_EN.md))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums` and `sequences` |
| Output | `True` if `nums` is the unique shortest supersequence |
| `nums` | Permutation of `1` to `n` |
| `sequences[i]` | Subsequence constraint |
| Main idea | Unique topological ordering |

Example function shape:

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

## Examples

Example 1:

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

Constraints:

```text
1 before 2
1 before 3
```

After placing `1`, both `2` and `3` are possible.

So there are two valid shortest supersequences:

```python
[1, 2, 3]
[1, 3, 2]
```

Answer:

```python
False
```

Example 2:

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

Only the order `1 before 2` is known.

The shortest supersequence can be:

```python
[1, 2]
```

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

Answer:

```python
False
```

Example 3:

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

Constraints:

```text
1 before 2
1 before 3
2 before 3
```

These force exactly:

```python
[1, 2, 3]
```

Answer:

```python
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:

```python
nums = [1, 2, 3]
```

we need evidence that:

```text
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:

```python
[5, 2, 6, 3]
```

means:

```text
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:

```text
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` | Build graph and process each edge once |
| Space | `O(n + m)` | Graph, indegree array, and queue |

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

## Implementation

```python
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:

```python
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:

```python
indegree = [0] * (n + 1)
```

For each adjacent pair in each sequence:

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

we add the ordering constraint:

```python
a -> b
```

Only new edges should increase indegree:

```python
if b not in graph[a]:
```

Then we collect all nodes with no prerequisites:

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

During topological sorting, uniqueness requires:

```python
if len(queue) != 1:
    return False
```

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

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

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

```python
indegree[nei] -= 1
```

When a neighbor becomes available, we push it:

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

Finally:

```python
return index == n
```

confirms that all nodes were processed.

## Testing

```python
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:

| Test | Why |
|---|---|
| Two possible orders | Checks non-unique reconstruction |
| Missing value in shortest order | Checks not shortest |
| Fully constrained order | Checks unique reconstruction |
| Longer example | Checks chained subsequences |
| Single node | Checks smallest valid input |
| Duplicate edge | Checks indegree is not overcounted |