How hard is LeetCode 444. Sequence Reconstruction?

LeetCode 444. Sequence Reconstruction is rated Medium on LeetCode.

What is the time complexity of LeetCode 444. Sequence Reconstruction?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 444. Sequence Reconstruction?

The Python solution on this page uses O(n + m) auxiliary space.

What topics does LeetCode 444. Sequence Reconstruction cover?

LeetCode 444. Sequence Reconstruction is tagged Graph, Topological Sort and Array on LeetCode.

Is LeetCode 444. Sequence Reconstruction a premium problem?

Yes. LeetCode 444. Sequence Reconstruction is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Sequence Reconstruction — LeetCode 444 Python Solution

MediumLeetCode PremiumGraphTopological SortArray

Problem: #444
Pattern: Topological Sort
Reading time: 4 min
Source: leetcode.com

The 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.

Example

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].

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 444. Sequence Reconstruction is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 444. Sequence Reconstruction?: LeetCode 444. Sequence Reconstruction is rated Medium on LeetCode.
What is the time complexity of LeetCode 444. Sequence Reconstruction?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 444. Sequence Reconstruction?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 444. Sequence Reconstruction cover?: LeetCode 444. Sequence Reconstruction is tagged Graph, Topological Sort and Array on LeetCode.
Is LeetCode 444. Sequence Reconstruction a premium problem?: Yes. LeetCode 444. Sequence Reconstruction is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.