Printing Array

Hard
0/120
Average time to solve is 45m
profile
Contributed by
2 upvotes
Asked in company
Google inc

Problem statement

You are given various subsequences of a particular array. You have to return the overall array from these given subsequences.

A subsequence of an array is a sequence that can be derived from the array by deleting 0 or more elements without changing the order. For example, for the given array [1, 2, 3, 4, 5], a few valid subsequences are [1, 3, 5], [2, 4], [1, 2, 3, 4, 5].

For Example: 
Consider the subsequences = [[1,3,9], [3,9,5]], for the given subsequences the output array could be [1, 3, 9, 5] as: 
1 is before 3 and 9
5 is after 3 and 9
3 is before 9
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases. The description of  ‘T’ test cases follows.

The first line of each test case contains an integer ‘N’ denoting the number of subsequences.

The next ‘N’ lines contain space-separated integers of the given subsequence.
Output format : 
For each test case, print "CORRECT" if the array formed with the subsequences is correct. Otherwise, print "INCORRECT".

For each test case, print a separate line.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
1 <= M <= 10^3
0 <= arr[i] <= 10^6

Time limit: 1 sec
Sample Input 1:
2
2
1 5 9
1 3 5  
3
5 9
1 3 5
1 5 2
Sample Output 1:
CORRECT
CORRECT
Explanation of Sample Input 1:
For the first test case, subsequences given = [[1, 3, 9], [3, 9, 5]], for the given subsequences the output array could be [1, 3, 9, 5] as: 
1 is before 3 and 9
5 is after 3 and 9
3 is before 9
Hence the answer [1, 3, 9, 5]

For the second test case,  sub sequences given = [[5, 9], [1, 3, 5], [1, 5, 2]], for the given subsequences the output array could be [1, 3, 5, 2, 9] or [1, 3, 5, 9, 2] as: 
9 comes after 5
5 comes after 1 and 3
2 comes after 5 
Hence one of the answer is [1, 3, 5, 2, 9]
Sample Input 2:
1
4
0 1
0 3
1 2
3 2
Sample Output 2:
CORRECT
Hint

Can you make a graph from the given arrays?

Approaches (2)
Topological Sort

In this approach, we know that a number appearing before any other number in a subsequence will occur before the final array. Therefore the ordering of the numbers will remain the same.

We will create a directed graph from the given subsequences, which will be acyclic. Then will perform a topological search on the graph.

We will create a topologicalSort(node, graph, visited, nodes) which will perform a topological sort on the graph. Here node is the current node, visited is a set of previously visited nodes, and nodes are the list of nodes in topological order.

 

Algorithm:

  • In the function topologicalSort(node, graph, visited, nodes)
    • Insert node in the visited set
    • Iterate children through graph[node]
      • If children in not in visited
        • Call topologicalSort(children, graph, visited, nodes)
    • Insert node into nodes
  • Initialize an empty map graph
  • Iterate subseq through subsequences
    • Iterate j from 1 to size of subseq - 1
      • If subseq[j - 1] not in graph
        • Set subseq[j - 1] as an empty array
      • If subseq[j] not in the graph
        • Set subseq[j] as an empty array
      • Insert subseq[j] into graph[subseq[j - 1]]
  • Set nodes as an empty array
  • Set visited as an empty set
  • iterate node through the graph
    • If node is not in visited
      • call topologicalSort(node, graph, visited, nodes)
  • Reverse the array nodes
  • Finally, return array nodes
Time Complexity

O(N*M), Where N is the number of subsequences and M is the average subsequence size.

 

The above algorithm is a topological sort algorithm with costs O(N * M) time. Hence the final time complexity is O(N*M).

Space Complexity

O(N*M), Where N is the number of subsequences and M is the average subsequence size.

 

The size of the nodes list can contain N*M elements in the worst case, and the space complexity of DFS is O(N). Hence the overall space complexity is O(N*M + N) = O(N*M).

Code Solution
(100% EXP penalty)
Printing Array
Full screen
Console