Problem Description

You are given an integer array nums of length n that is a permutation of integers from 1 to n. You also have a 2D array sequences where each sequences[i] is a subsequence of nums.

Your task is to determine if nums is both:

1. The shortest possible supersequence that contains all given subsequences
2. The only unique shortest supersequence

A supersequence is a sequence that contains all the given subsequences as its subsequences. A subsequence is derived from a sequence by deleting some or no elements without changing the order of remaining elements.

For example:

• Given sequences = [[1,2],[1,3]], there are two possible shortest supersequences: [1,2,3] and [1,3,2]. Since there are multiple valid shortest supersequences, the answer would be false.
• Given sequences = [[1,2],[1,3],[1,2,3]], the only shortest supersequence is [1,2,3]. While [1,2,3,4] is also a valid supersequence, it's not the shortest. Since there's only one shortest supersequence, the answer would be true.

The solution uses topological sorting to solve this problem. For each consecutive pair of elements (a, b) in every subsequence, we create a directed edge a → b in a graph. We then perform topological sorting using a queue-based approach:

1. Build a directed graph from the subsequences and calculate in-degrees for each node
2. Add all nodes with in-degree 0 to a queue
3. Process nodes one at a time when the queue has exactly one element (ensuring unique ordering)
4. For each processed node, reduce the in-degree of its neighbors and add any that reach 0 to the queue
5. If at any point the queue has more than one element, multiple orderings are possible
6. Return true if the queue remains empty after processing (unique shortest supersequence exists), false otherwise

Intuition

The key insight is recognizing that this problem is about finding a unique topological ordering. Each subsequence gives us ordering constraints - if element a appears before element b in a subsequence, then a must appear before b in any valid supersequence.

Think of it this way: each subsequence tells us "these elements must appear in this relative order." If we combine all these constraints, we're essentially building a directed graph where an edge a → b means "a must come before b."

The critical observation is that for nums to be the only shortest supersequence, there must be exactly one valid way to order all elements while respecting these constraints. This happens when at each step of building the sequence, we have exactly one choice of which element to place next.

In topological sorting terms, this means:

• When we start, there should be exactly one element with no prerequisites (in-degree 0)
• After placing that element, there should be exactly one new element that becomes available
• This pattern continues until all elements are placed

If at any point we have multiple elements with in-degree 0 simultaneously, it means we could choose any of them next, leading to multiple valid orderings. For example, if both elements 2 and 3 have no prerequisites after placing element 1, we could create either [1,2,3,...] or [1,3,2,...] as valid supersequences.

The shortest supersequence will have length n (using each number exactly once). By performing topological sorting and checking that we always have exactly one choice at each step, we can verify both that nums is the shortest possible supersequence and that it's the only one.

Solution Approach

The implementation uses topological sorting with a queue to verify if there's a unique ordering:

1. Graph Construction:

• Create an adjacency list g with n empty lists (one for each number 1 to n)
• Create an indeg array to track the in-degree of each node
• For each subsequence, iterate through consecutive pairs using pairwise(seq)
• For each pair (a, b), add a directed edge from a-1 to b-1 (converting to 0-indexed)
• Increment the in-degree of b-1

2. Initialize Queue:

• Use a deque to store all nodes with in-degree 0
• These are the nodes that can be placed first (no prerequisites)

3. Process Nodes:

• While the queue has exactly one element:
  • Remove the single element i from the queue
  • For each neighbor j of node i:
    • Decrement indeg[j] by 1 (removing the edge i → j)
    • If indeg[j] becomes 0, add j to the queue
• The loop continues only when there's exactly one choice at each step

4. Verify Result:

• After the loop ends, check if the queue is empty
• If len(q) == 0: All nodes were processed with a unique ordering → return true
• If len(q) > 0: Multiple nodes have in-degree 0 simultaneously, meaning multiple valid orderings exist → return false

The algorithm works because:

• If the queue ever has more than 1 element, the loop breaks, indicating multiple possible orderings
• If the queue becomes empty before all nodes are processed, there's a cycle (impossible since we have a valid permutation)
• Only when exactly n nodes are processed one-by-one with no ambiguity do we have a unique shortest supersequence

Time Complexity: O(m) where m is the total number of elements across all subsequences Space Complexity: O(n) for the graph and in-degree arrays

Example Walkthrough

Let's walk through the solution with nums = [1,2,3] and sequences = [[1,2], [1,3], [2,3]].

Step 1: Build the Graph

• From subsequence [1,2]: Add edge 1→2
• From subsequence [1,3]: Add edge 1→3
• From subsequence [2,3]: Add edge 2→3

Converting to 0-indexed:

• Node 0 (represents 1): edges to [1, 2]
• Node 1 (represents 2): edges to [2]
• Node 2 (represents 3): no outgoing edges

In-degrees after building:

• Node 0: in-degree = 0 (no incoming edges)
• Node 1: in-degree = 1 (edge from node 0)
• Node 2: in-degree = 2 (edges from nodes 0 and 1)

Step 2: Initialize Queue

• Only node 0 has in-degree 0
• Queue = [0]

Step 3: Process Nodes

Iteration 1:

• Queue has exactly 1 element (node 0), so continue
• Remove node 0, process its neighbors:
  • Neighbor 1: decrement in-degree from 1 to 0, add to queue
  • Neighbor 2: decrement in-degree from 2 to 1
• Queue = [1]

Iteration 2:

• Queue has exactly 1 element (node 1), so continue
• Remove node 1, process its neighbor:
  • Neighbor 2: decrement in-degree from 1 to 0, add to queue
• Queue = [2]

Iteration 3:

• Queue has exactly 1 element (node 2), so continue
• Remove node 2 (no neighbors to process)
• Queue = []

Step 4: Verify Result

• Queue is empty (length 0)
• All nodes were processed with exactly one choice at each step
• Return true - there is a unique shortest supersequence [1,2,3]

Counter-example: If we had sequences = [[1,2], [1,3]] instead:

• After processing node 0, both nodes 1 and 2 would have in-degree 0
• Queue = [1, 2] (length > 1)
• The loop would break immediately
• Return false - multiple valid orderings exist ([1,2,3] or [1,3,2])

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm performs the following operations:

• Building the graph: Iterating through all sequences and all adjacent pairs takes O(m) time, where m is the total number of edges (sum of lengths of all sequences minus the number of sequences)
• Initializing the indegree array: O(n) time
• Finding initial nodes with zero indegree: O(n) time
• BFS/Topological sort: Each node is processed once (O(n)), and each edge is traversed once when updating indegrees (O(m))

Total time complexity: O(n + m)

Space Complexity: O(n + m)

The algorithm uses:

• Graph adjacency list g: Stores all edges, requiring O(m) space
• Indegree array indeg: Stores indegree for each node, requiring O(n) space
• Queue q: In the worst case contains all nodes, requiring O(n) space

Total space complexity: O(n + m)

Where n is the number of nodes (length of nums) and m is the total number of edges across all sequences.

Common Pitfalls

1. Not Handling Duplicate Edges in the Graph

One critical pitfall is that the current implementation doesn't handle duplicate edges properly. When building the graph from subsequences, if the same edge appears multiple times (e.g., [1,2] appears in multiple subsequences), the in-degree gets incremented multiple times for the same relationship.

Problem Example:

nums = [1, 2, 3]
sequences = [[1, 2], [1, 2], [2, 3]]  # [1,2] appears twice

The current code would set in_degrees[1] to 2 instead of 1, leading to incorrect results.

Solution: Use a set to track edges and only increment in-degree once per unique edge:

def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
    n = len(nums)
    adjacency_list = [[] for _ in range(n)]
    in_degrees = [0] * n
  
    # Track edges to avoid duplicates
    edges_seen = set()
  
    for sequence in sequences:
        for first_val, second_val in pairwise(sequence):
            from_node = first_val - 1
            to_node = second_val - 1
            edge = (from_node, to_node)
          
            # Only process each unique edge once
            if edge not in edges_seen:
                edges_seen.add(edge)
                adjacency_list[from_node].append(to_node)
                in_degrees[to_node] += 1
  
    # Rest of the code remains the same...

2. Not Validating Input Values Are Within Range

The code assumes all values in subsequences are valid (between 1 and n). Invalid values would cause index out of bounds errors.

Problem Example:

nums = [1, 2, 3]
sequences = [[1, 4]]  # 4 is out of range

Solution: Add validation before processing:

for sequence in sequences:
    for val in sequence:
        if val < 1 or val > n:
            return False  # Invalid value in subsequence
    # Continue with pairwise processing...

3. Not Checking if All Numbers Are Covered

The algorithm might return true even if not all numbers from nums appear in the subsequences, as it only checks the topological ordering of edges that exist.

Problem Example:

nums = [1, 2, 3]
sequences = [[1, 2]]  # 3 is never mentioned

Solution: Track which numbers appear in subsequences and verify all are present:

seen_numbers = set()
for sequence in sequences:
    seen_numbers.update(sequence)

if seen_numbers != set(range(1, n + 1)):
    return False  # Not all numbers are covered

4. Empty Subsequences Handling

The code doesn't explicitly handle empty subsequences, though pairwise() naturally handles them by producing no pairs.

Better Practice: Filter out empty subsequences explicitly for clarity:

sequences = [seq for seq in sequences if len(seq) > 0]