444. Sequence Reconstruction


Problem Description

The problem presents us with an interesting challenge. We're given two things: an array nums which is a permutation of integers from 1 to n, and a 2D array sequences which contains subsequences of nums. Our goal is to check if the array nums is the unique and shortest supersequence of all the subsequences in sequences. A supersequence is a sequence that contains all other subsequences as part of it without changing the order of elements in those subsequences. The twist is that we need to determine if nums is not just any supersequence, but the shortest possible one that exists uniquely for the given subsequences.

To further understand the problem, consider that a supersequence should accommodate all the ordering requirements specified by each subsequence. If sequences contains [1,2] and [1,3] as subsequences, the supersequence should start with 1 and then have 2 and 3 in any order because 1 comes before both 2 and 3 in both subsequences. However, if we have a subsequence [1,2,3], it now dictates the order that 2 must come before 3, which gives us only one possibility for the supersequence: [1,2,3].

Understanding this, the challenge becomes checking if nums is this strictly defined shortest supersequence and that no other supersequence, which is different from nums but still meets the criteria, exists.

Intuition

To tackle this problem, we can draw from concepts used in graphs, specifically topological sorting. We can create a directed graph where each number in sequences represents a node, and the relationship between the numbers represents the directed edges. The crucial insight is that if nums is indeed the unique shortest supersequence, then the topological sort of this graph should yield one and only one specific order.

Here's how we approach it:

  1. Build a graph - We create a directed graph where each edge from a to b shows that a precedes b in at least one of the subsequences.

  2. Calculate indegrees - The indegree of a node is the number of edges coming into it. For the purpose of topological sorting, nodes with an indegree of 0 can be considered as starting points.

  3. Queue for processing - Nodes with 0 indegree are added to a queue to process them one by one. At each step, we should only have one node in our queue if nums is to be the unique shortest supersequence. Having more than one node means we have multiple ways to arrange the supersequence, and hence nums wouldn't be the unique supersequence.

  4. Reduce indegrees - As we process a node, we reduce the indegree of its directed neighbors by 1. If any neighbor's indegree reaches 0, it means that all its prerequisites are processed, and it can be added to the queue.

  5. Check queue size - If at any point we have more than one element in the queue, it implies multiple possible sequences, and we return false.

  6. Final check - If we never encounter a queue with more than one element and all nodes have been processed, then nums is the unique shortest supersequence, hence we return true.

This method allows us to determine not only if nums is a supersequence but also if it is the unique and shortest one. It's a clever application of graph theory to sequence reconstruction.

Learn more about Graph and Topological Sort patterns.

Solution Approach

The solution provided is a direct implementation of the topological sort algorithm used on a directed graph. The algorithm checks whether there is a unique way to reconstruct the permutation sequence given the array of subsequences. Here is a step-by-step explanation of the algorithm, mapping them to the respective parts of the code:

  1. Constructing the directed graph and calculating indegrees:

    • A directed graph is built using a dictionary g where each key-value pair is a node and its list of neighboring nodes (the nodes that follow it directly in the permutation).
    • The indegrees are stored in indeg, an array where each index corresponds to a node and its value represents the number of edges coming into that node.
    • The graph and the indegrees are generated by iterating over each pair of adjacent elements (a, b) in every subsequence using pairwise(seq) and doing the following:
      • Append b - 1 to the adjacency list of node a - 1 in the graph (g[a - 1].append(b - 1)).
      • Increase the indegree of node b - 1 by 1 (indeg[b - 1] += 1).
    1g = defaultdict(list)
    2indeg = [0] * len(nums)
    3for seq in sequences:
    4    for a, b in pairwise(seq):
    5        g[a - 1].append(b - 1)
    6        indeg[b - 1] += 1
  2. Initializing the queue:

    • A deque q is created to hold nodes with an indegree of 0, i.e., nodes that are not preceded by another node in any subsequence and hence can start the permutation.
    1q = deque(i for i, v in enumerate(indeg) if v == 0)
  3. Processing the nodes:

    • The nodes are processed one by one from the queue. The uniqueness check for the supersequence is done here - if there's ever more than one node with indegree 0, we return False. This condition indicates that there is more than one valid sequence, which violates the problem's constraint requiring a unique shortest supersequence.
      1while q:
      2    if len(q) > 1:
      3        return False
      4    i = q.popleft()
      5    ...
    • For each node taken from the queue, the algorithm decrements the indegree of all its neighbors because the current node has been processed and therefore is no longer a prerequisite for its neighbors.
      1for j in g[i]:
      2    indeg[j] -= 1
      3    if indeg[j] == 0:
      4        q.append(j)
  4. Check if the sequence is reconstructable:

    • After processing all nodes, if the sequence is reconstructable as a unique shortest supersequence, the program would have successfully popped all nodes from the queue (without finding a condition where there's more than one node that can be processed next), and therefore it returns True.
    1return True

This algorithm ensures that if there is more than one way to order subsequences, it will be caught during the processing stage, leading to a False result. Conversely, if nums is the unique shortest supersequence, it will satisfy this single-path condition throughout the entire process, leading to a True result.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example:

Consider an array nums that is a permutation of integers from 1 to 3, which is [1, 2, 3], and a 2D array sequences that contains subsequences of nums, which is [[1, 2], [1, 3]].

Now let's walk through the solution:

  1. Constructing the directed graph and calculating indegrees:

    • We initialize a graph g and array indeg to store the indegrees. From the subsequences, we can see that 1 precedes both 2 and 3. In terms of indegrees, 1 has an indegree of 0, and 2 and 3 both have indegrees of 1 since they are each preceded once by 1.
    • The graph g will have edges from 1 to 2 and from 1 to 3.
  2. Initializing the queue:

    • We initialize a queue q and add the node 1 to it since it's the only number with an indegree of 0.
  3. Processing the nodes:

    • We pop 1 from the queue and decrement the indegrees of its neighbors, which are 2 and 3. After decrementing, both nodes have indegrees of 0 and are added to the queue. However, because we can only have one node in the queue for the sequence to be unique, at this point, the algorithm would detect that there is more than one node with indegree 0 and return False.

Using the above example, it's clear that the permutation nums = [1, 2, 3] is not the unique shortest supersequence for the given sequences = [[1, 2], [1, 3]] since we ended up with two nodes in the queue at the same time, indicating that there are multiple possible sequences. The function would thus conclude the permutation sequence cannot be uniquely reconstructed and return False.

Solution Implementation

1from collections import defaultdict, deque
2from itertools import pairwise
3
4class Solution:
5    def sequenceReconstruction(self, originalSequence: List[int], sequences: List[List[int]]) -> bool:
6        # Create a graph and an in-degree list initialized with zeros for all elements
7        graph = defaultdict(list)
8        in_degree = [0] * len(originalSequence)
9      
10        # Build the graph and in-degree list using input sequences
11        for sequence in sequences:
12            for prev, current in pairwise(sequence):
13                graph[prev - 1].append(current - 1)  # Nodes are 0-based in the graph
14                in_degree[current - 1] += 1  # Increment in-degree for the current node
15      
16        # Queue for nodes with zero in-degree
17        queue = deque(node for node, degree in enumerate(in_degree) if degree == 0)
18      
19        # Process the graph using the queue
20        while queue:
21            # If there's more than one node with in-degree zero, the original sequence is not unique
22            if len(queue) > 1:
23                return False
24            node = queue.popleft()
25          
26            # Go through all the adjacent nodes
27            for adjacent in graph[node]:
28                # Decrement in-degree and if it becomes zero, add to the queue
29                in_degree[adjacent] -= 1
30                if in_degree[adjacent] == 0:
31                    queue.append(adjacent)
32      
33        # Return True if the original sequence can be uniquely reconstructed
34        return all(degree == 0 for degree in in_degree)
35
1class Solution {
2    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
3        int n = nums.length; // number of elements in the original sequence
4        int[] inDegrees = new int[n]; // array to record the number of incoming edges for each vertex in the graph
5        List<Integer>[] graph = new List[n]; // adjacency list to represent the graph
6        Arrays.setAll(graph, k -> new ArrayList<>()); // initialize the adjacency list
7      
8        // Convert sequences into a directed graph
9        for (List<Integer> seq : sequences) {
10            for (int i = 1; i < seq.size(); ++i) {
11                int from = seq.get(i - 1) - 1; // convert 1-based index to 0-based index
12                int to = seq.get(i) - 1; // convert 1-based index to 0-based index
13                graph[from].add(to); // add an edge from 'from' to 'to'
14                inDegrees[to]++; // increase the in-degree of the 'to' node
15            }
16        }
17      
18        Deque<Integer> queue = new ArrayDeque<>(); // queue to perform topological sorting
19        // Find all nodes with no incoming edges and add them to the queue
20        for (int i = 0; i < n; ++i) {
21            if (inDegrees[i] == 0) {
22                queue.offer(i);
23            }
24        }
25      
26        // Perform topological sort and check whether the original sequence is uniquely reconstructible
27        while (!queue.isEmpty()) {
28            if (queue.size() > 1) {
29                // More than one node with no incoming edges means there can be more than one sequence
30                return false;
31            }
32            int node = queue.poll(); // remove the next node from the queue
33            // Iterate over all the neighbors of the current node
34            for (int neighbor : graph[node]) {
35                if (--inDegrees[neighbor] == 0) { // if the in-degree becomes 0, add the neighbor to the queue
36                    queue.offer(neighbor);
37                }
38            }
39        }
40      
41        // If the graph has been fully traversed and a unique sequence is determined, return true
42        return true;
43    }
44}
45
1class Solution {
2public:
3    // Function to determine if a sequence can be reconstructed to match the original sequence
4    bool sequenceReconstruction(vector<int>& originalSeq, vector<vector<int>>& sequences) {
5        int n = originalSeq.size();
6        vector<vector<int>> graph(n, vector<int>());
7        vector<int> inDegree(n, 0);
8
9        // Construct the graph and count incoming degrees
10        for (const auto& seq : sequences) {
11            for (int i = 1; i < seq.size(); ++i) {
12                int from = seq[i - 1] - 1; // Convert to 0-based index
13                int to = seq[i] - 1; // Convert to 0-based index
14                graph[from].push_back(to);
15                ++inDegree[to];
16            }
17        }
18
19        // Initialize a queue with all nodes that have an in-degree of 0
20        queue<int> nodesWithNoIncomingEdges;
21        for (int i = 0; i < n; ++i) {
22            if (inDegree[i] == 0) {
23                nodesWithNoIncomingEdges.push(i);
24            }
25        }
26
27        // Process the nodes
28        while (!nodesWithNoIncomingEdges.empty()) {
29            // If there is more than one node with no incoming edges, return false
30            // Because we should be able to determine the order unambiguously
31            if (nodesWithNoIncomingEdges.size() > 1) return false;
32
33            int currentNode = nodesWithNoIncomingEdges.front();
34            nodesWithNoIncomingEdges.pop();
35
36            // Decrease the in-degree of neighboring nodes and add to queue if in-degree becomes 0
37            for (int neighbor : graph[currentNode]) {
38                if (--inDegree[neighbor] == 0) {
39                    nodesWithNoIncomingEdges.push(neighbor);
40                }
41            }
42        }
43      
44        // Return true if we can reconstruct the sequence uniquely
45        return true;
46    }
47};
48
1// TypeScript does not directly support typing for a 2D array with specific inner array lengths, so we use number[][] to represent a list of sequences.
2// Represents the original sequence to be reconstructed
3let originalSeq: number[] = [];
4
5// Represents the sequences of numbers which are subsequences of the original sequence
6let sequences: number[][] = [];
7
8// Construct a directed graph and in-degree array from the sequences
9let graph: number[][];
10let inDegree: number[];
11
12// Initialize the inDegree array and adjacency list graph from sequences
13function buildGraph(seqList: number[][], nodeCount: number): void {
14  graph = new Array(nodeCount);
15  inDegree = new Array(nodeCount).fill(0);
16
17  for (let i = 0; i < nodeCount; i++) {
18    graph[i] = [];
19  }
20
21  for (const seq of seqList) {
22    for (let i = 1; i < seq.length; i++) {
23      let from = seq[i - 1] - 1;
24      let to = seq[i] - 1;
25      graph[from].push(to);
26      inDegree[to]++;
27    }
28  }
29}
30
31// Function to determine if a sequence can be reconstructed to match the original sequence
32function sequenceReconstruction(originalSeq: number[], sequences: number[][]): boolean {
33  const n: number = originalSeq.length;
34  buildGraph(sequences, n); // Build the graph and inDegree arrays for the given sequences
35
36  const nodesWithNoIncomingEdges: number[] = [];
37
38  // Find all nodes with no incoming edges
39  for (let i = 0; i < n; i++) {
40    if (inDegree[i] === 0) {
41      nodesWithNoIncomingEdges.push(i);
42    }
43  }
44
45  // Process the nodes while there are nodes with no incoming edges
46  let index = 0;
47  while (nodesWithNoIncomingEdges.length > 0) {
48    // If there is more than one node with no incoming edges,
49    // the sequence cannot be uniquely reconstructed
50    if (nodesWithNoIncomingEdges.length > 1) return false;
51  
52    // The next node should match the next element in the original sequence
53    let currentNode = nodesWithNoIncomingEdges.shift()!;
54    if (originalSeq[index++] !== currentNode + 1) return false;
55
56    // Decrease the in-degree of neighboring nodes
57    // If the in-degree becomes 0, add to the queue
58    graph[currentNode].forEach(neighbor => {
59      if (--inDegree[neighbor] === 0) {
60        nodesWithNoIncomingEdges.push(neighbor);
61      }
62    });
63  }
64
65  // The sequence can be reconstructed if all the nodes in the original sequence are processed
66  return index === n;
67}
68
69// Example usage:
70// originalSeq = [1, 2, 3, 4];
71// sequences = [[1, 2], [2, 3], [3, 4]];
72// console.log(sequenceReconstruction(originalSeq, sequences)); // Should output true
73

Time and Space Complexity

The time complexity of the given code is O(V + E), where V is the number of vertices (numbers) in nums and E is the total number of edges (order relationships) in sequences. This is because building the graph (adjacency list) requires traversing each pair in sequences, and then using BFS to traverse through the constructed graph only once.

The space complexity is also O(V + E), which stems from the space required to store the graph g and indegree array indeg. The adjacency list g stores at most E edges, whereas the indegree array indeg has space for V vertices. The queue q in the BFS procedure will also require at most V space in the worst case (when all vertices have zero indegree at the same time).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does quick sort divide the problem into subproblems?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.