> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Sequence Reconstruction Python Solution

> Tested Python solution for LeetCode 444 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 444, [Medium](/catalog/medium). Topics: [Graph](/catalog/topics/graph), [Topological Sort](/catalog/topics/topological-sort), [Array](/catalog/topics/array), Directed Acyclic Graph. [View on LeetCode](https://leetcode.com/problems/sequence-reconstruction/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 444   # by problem number
lcpy gen -s sequence_reconstruction   # by problem name
```

## Problem

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.

### Examples

```
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]. Since nums is not the only shortest supersequence, we return false.
```

```
Input: nums = [1,2,3], sequences = [[1,2]]
Output: false
Explanation: The shortest possible supersequence is [1,2]. Since nums is not the shortest supersequence, we return false.
```

```
Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
Output: true
Explanation: The shortest possible supersequence is [1,2,3]. Since nums is the only shortest supersequence, we return true.
```

### Constraints

* `n == nums.length`
* `1 <= n <= 10^4`
* `nums` is a permutation of all the integers in the range `[1, n]`.
* `1 <= sequences.length <= 10^4`
* `1 <= sequences[i].length <= 10^4`
* `1 <= sum(sequences[i].length) <= 10^5`
* `1 <= sequences[i][j] <= n`
* All the arrays of `sequences` are **unique**.
* `sequences[i]` is a subsequence of `nums`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sequence_reconstruction/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sequence_reconstruction/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(total sequence length)
    # Space: O(n)
    def sequence_reconstruction(self, nums: list[int], sequences: list[list[int]]) -> bool:
        pos = {v: i for i, v in enumerate(nums)}
        following: set[tuple[int, int]] = set()
        for seq in sequences:
            for i in range(len(seq) - 1):
                a, b = seq[i], seq[i + 1]
                if a not in pos or b not in pos or pos[a] >= pos[b]:
                    return False
                following.add((a, b))
        return all((nums[i], nums[i + 1]) in following for i in range(len(nums) - 1))
```

## Complexity

| Time | Space |
| - | - |
| O(total sequence length) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.