Last Updated: 1 Apr, 2021
Sequence Reconstruction
Moderate
Asked in companies
You are given a sequence ‘primary’ and a sequence of sequences ‘secondary.’ The sequence ‘primary’ is a permutation of numbers from 1 to N. You need to find if the sequence ‘primary’ is the only shortest common supersequence of sequences in ‘secondary’.
The shortest common supersequence of two sequences, ‘A’ and ‘B’, is the shortest sequence such that ‘A’ and ‘B’ are subsequences of it.
Note :
The range of elements in the ‘secondary’ sequence varies from 1 to N.
For Example :
If primary = [ 1, 2, 3 ] and secondary = [ [ 1, 2 ], [ 1, 3 ] ]
[ 1, 2, 3 ] is shortest common supersequence of [ 1, 2 ] and [ 1, 3 ]. But [ 1, 3, 2 ] is also a shortest common super sequence of [ 1, 2 ] and [ 1, 3 ]. As [ 1, 2, 3 ] is not the only shortest supersequence, you need to return false.
Input Format :
The first line contains ‘ T ‘, denoting the number of test cases.
The first line of each test case contains three space-separated integers, N - number of elements in ‘primary’ sequence, ‘ X ‘ - number of sequences in ‘secondary’ sequence, and ‘ Y ‘ - number of elements in each sequence of ‘secondary’ sequence.
Each test case’s second line contains ‘ N ’ space-separated integers denoting elements of the ‘primary’ sequence.
The following ‘ X ‘ lines of each test case contain ‘ Y ‘ space-separated integers.
Output Format :
For each test case, return “ True “ if ‘primary’ is the only shortest supersequence of all the sequences in the ‘secondary’ sequence. Otherwise, return “ False “.
Print the output of each test case in a separate line.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= primary[ i ] <= N
1 <= X, Y <= 10^3
Time Limit: 1 sec
Approaches
We will represent the sequences in the ‘secondary’ sequence by a directed graph and find its topological sort order. If there is only one topological sort order, then we can say that the ‘primary’ sequence is the only shortest common supersequence.
At first, if the number of distinct elements in all the sequences in ‘secondary’ is less than the number of elements in ‘primary,’ i.e., ‘N’, then ‘primary’ can never be the shortest common supersequence.
We will calculate indegree for every vertex of the graph and find the vertices having ‘0’ indegree. Suppose at any moment there come two vertices with ‘0’ indegree. In that case, that means we have two choices for the topological sort order, and there can never be a unique common supersequence; otherwise, we will add this vertex to the topological sort order and decrement the in-degree of all the vertices connected to it.
If the topological sort order is the same as the ‘primary’ sequence, then we can say that the ‘primary’ sequence is the shortest common super sequence of all the sequences in ‘secondary’.
Algorithm
- Create a map ‘ adj ‘to store edges of all the vertices and a map ‘ indegree ‘ that will store the indegree of all the vertices.
- Initialize all the keys of maps with all the elements in the sequences in ‘secondary.’
- If the size of ‘ adj ‘ is not equal to ‘ primary ‘, return false.
- Put all the sequences in ‘secondary’ as an edge from the previous element to the current element in the ‘adj’ map and increment count of indegree of the current element in the ‘indegree’ map.
- Initialize a queue ‘ q ‘ that will store the elements with ‘ 0’ indegree.
- Traverse the map ‘indegree’ and push the elements with ‘ 0 ‘ indegree in ‘ q ‘.
- Create a vector ‘res’ to store the topologically sorted order.
- Run a loop until the queue is not empty.
- If the size of ‘ q ‘ > 1, i.e., there is more than one element with ‘ 0 ‘ indegree, return false.
- Else, store the queue’s front element in ‘ num ‘ and pop this from the queue.
- Push ‘ num ‘ to ‘ res ‘.
- Decrement indegree of all the vertices connected to it by ‘ 1 ‘ and if indegree of any vertices became ‘ 0 ‘, push it to the queue.
- If for any key in ‘indegree’, value > 0, return false.
- If the order of elements in ‘res’ is the same as the order in ‘ primary ‘, return true. Otherwise, return false.
Let us understand the above approach with an example.
Let primary = [ 1, 2, 3 ] and secondary = [ [ 1, 2 ], [ 1, 3 ] ].
‘ adj ’ map will contain values as -
1 -> 2 , 3
2 -> Null
3 -> Null
‘indegree’ map will contain values as
1 -> 0
2 -> 1
3 -> 1
Now we will push elements with ‘ 0 ‘ indegree and decrement indegree of all vertices connected to it.
Initially push ‘ 1’ to ‘res’ and decrement indegree of ‘2’ and ‘3.’
Now Indegree of both ‘2’ and ‘3’ are ‘0’, which means we have two choices, and the supersequence can not be unique. So the answer will be false.