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:
-
Build a graph - We create a directed graph where each edge from
a
tob
shows thata
precedesb
in at least one of the subsequences. -
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. -
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 ifnums
is to be the unique shortest supersequence. Having more than one node means we have multiple ways to arrange the supersequence, and hencenums
wouldn't be the unique supersequence. -
Reduce indegrees - As we process a node, we reduce the indegree of its directed neighbors by
1
. If any neighbor's indegree reaches0
, it means that all its prerequisites are processed, and it can be added to the queue. -
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
. -
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 returntrue
.
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:
-
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 usingpairwise(seq)
and doing the following:- Append
b - 1
to the adjacency list of nodea - 1
in the graph (g[a - 1].append(b - 1)
). - Increase the indegree of node
b - 1
by 1 (indeg[b - 1] += 1
).
- Append
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
- A directed graph is built using a dictionary
-
Initializing the queue:
- A deque
q
is created to hold nodes with an indegree of0
, 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)
- A deque
-
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 returnFalse
. 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)
- 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
-
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
- 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
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 EvaluatorExample 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:
-
Constructing the directed graph and calculating indegrees:
- We initialize a graph
g
and arrayindeg
to store the indegrees. From the subsequences, we can see that1
precedes both2
and3
. In terms of indegrees,1
has an indegree of0
, and2
and3
both have indegrees of1
since they are each preceded once by1
. - The graph
g
will have edges from1
to2
and from1
to3
.
- We initialize a graph
-
Initializing the queue:
- We initialize a queue
q
and add the node1
to it since it's the only number with an indegree of0
.
- We initialize a queue
-
Processing the nodes:
- We pop
1
from the queue and decrement the indegrees of its neighbors, which are2
and3
. After decrementing, both nodes have indegrees of0
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 indegree0
and returnFalse
.
- We pop
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.
How does quick sort divide the problem into subproblems?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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.