# 444. Sequence Reconstruction

## Description

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.

Example 1:

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].
The sequence [1,2] is a subsequence of both: [1,2,3] and [1,3,2].
The sequence [1,3] is a subsequence of both: [1,2,3] and [1,3,2].
Since nums is not the only shortest supersequence, we return false.


Example 2:

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


Example 3:

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


Constraints:

• n == nums.length
• 1 <= n <= 104
• nums is a permutation of all the integers in the range [1, n].
• 1 <= sequences.length <= 104
• 1 <= sequences[i].length <= 104
• 1 <= sum(sequences[i].length) <= 105
• 1 <= sequences[i][j] <= n
• All the arrays of sequences are unique.
• sequences[i] is a subsequence of nums.

## Solutions

• class Solution {
public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
int n = nums.length;
int[] indeg = new int[n];
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var seq : sequences) {
for (int i = 1; i < seq.size(); ++i) {
int a = seq.get(i - 1) - 1, b = seq.get(i) - 1;
indeg[b]++;
}
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.offer(i);
}
}
while (!q.isEmpty()) {
if (q.size() > 1) {
return false;
}
int i = q.poll();
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.offer(j);
}
}
}
return true;
}
}

• class Solution {
public:
bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
int n = nums.size();
vector<vector<int>> g(n);
vector<int> indeg(n);
for (auto& seq : sequences) {
for (int i = 1; i < seq.size(); ++i) {
int a = seq[i - 1] - 1, b = seq[i] - 1;
g[a].push_back(b);
++indeg[b];
}
}
queue<int> q;
for (int i = 0; i < n; ++i)
if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
if (q.size() > 1) return false;
int i = q.front();
q.pop();
for (int j : g[i])
if (--indeg[j] == 0) q.push(j);
}
return true;
}
};

• class Solution:
def sequenceReconstruction(
self, nums: List[int], sequences: List[List[int]]
) -> bool:
g = defaultdict(list)
indeg = [0] * len(nums)
for seq in sequences:
for a, b in pairwise(seq):
g[a - 1].append(b - 1)
indeg[b - 1] += 1
q = deque(i for i, v in enumerate(indeg) if v == 0)
while q:
if len(q) > 1:
return False
i = q.popleft()
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return True


• func sequenceReconstruction(nums []int, sequences [][]int) bool {
n := len(nums)
g := make([][]int, n)
indeg := make([]int, n)
for _, seq := range sequences {
for i := 1; i < len(seq); i++ {
a, b := seq[i-1]-1, seq[i]-1
g[a] = append(g[a], b)
indeg[b]++
}
}
q := []int{}
for i, v := range indeg {
if v == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
if len(q) > 1 {
return false
}
i := q[0]
q = q[1:]
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
}
}
return true
}

• function sequenceReconstruction(nums: number[], sequences: number[][]): boolean {
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => []);
const indeg: number[] = Array(n).fill(0);
for (const seq of sequences) {
for (let i = 1; i < seq.length; ++i) {
const [a, b] = [seq[i - 1] - 1, seq[i] - 1];
g[a].push(b);
++indeg[b];
}
}
const q: number[] = indeg.map((v, i) => (v === 0 ? i : -1)).filter(v => v !== -1);
while (q.length === 1) {
const i = q.pop()!;
for (const j of g[i]) {
if (--indeg[j] === 0) {
q.push(j);
}
}
}
return q.length === 0;
}