Sequence Reconstruction

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
15 upvotes
Asked in companies
AmazonGoldman Sachs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 2 3
2 4 3 1
2 3 1
4 3 1
3 3 2
1 2 3
1 2
1 3
2 3
Simple Output 1 :
False
True
Explanation Of Sample Input 1 :
Test Case 1: The ‘primary’ sequence given is [ 2, 4, 3, 1 ]. But this is not the only common supersequence as [ 4, 2, 3, 1 ] is also a common supersequence of [ 2, 3, 1 ] and [ 4, 3, 1 ].

Test Case 2: [ 1, 2, 3 ] is the only shortest common supersequence of [ 1, 2 ], [ 1, 3 ] and [ 2, 3 ].
Sample Input 2 :
2
3 1 2
1 3 2
1 2
5 1 5
1 4 5 2 3
1 4 5 2 3
Sample Output 2 :
False
True
Hint

Can you think of topological sorting?

Approaches (1)
Topological Sorting

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.

Time Complexity

O( N + (X*Y) ), where ‘ N ‘ is the number of elements in ‘primary’, ‘ X ‘ and ‘ Y ‘is the number and the length of sequences in ‘secondary’.

 

We are creating a graph where the number of vertices is ‘ N ‘ and the maximum number of edges is X*Y. As traversing a graph takes O( V+E ) time, so the overall time complexity is O( N + (X*Y) ).

Space Complexity

O( N + (X*Y) ), where ‘ N ‘ is the number of elements in ‘primary’, ‘ X ‘ and ‘ Y ‘is the number and the length of sequences in ‘secondary’.

 

We are creating a map to store all the vertices and their edges, making space complexity. 

O( N + (X*Y) ).

Code Solution
(100% EXP penalty)
Sequence Reconstruction
Full screen
Console