Last Updated: 17 Sep, 2021

Printing Array

Hard

Asked in company

Solve now

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

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

In this approach, like the previous approach, we will find the topological sort of directed graph. Here we will use Kahn’s Algorithm.

According to Kahn algorithm:

Pick all nodes with 0 in-degree and insert them into the topological sort
Then delete the nodes from the graph and pick the next nodes with 0 in-degree
Repeat this until all nodes are processed

We create topologicalSort(graph), which will return the topological sort of the graph

Algorithm:

In the function topologicalSort(graph)
- Initialize an empty map inDegree and set the in-degree of all nodes as 0
- Iterate node through the graph
  - Iterate child through graph[node]
    - Increase inDegree[child] by 1
- Create an empty queue queue
  - Iterate node through graph
    - If inDegree[node] is equal to 0
      - Insert node into queue
- Create an empty array nodes
- While queue is not empty
  - Set currNode as the front of queue and remove the front element from queue
  - Iterate child through graph[currNode]
    - Decrease inDegree[child] by 1
    - If inDegree[child] is equal to 0,
      - Insert child into the queue
- Return 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] is not in the graph
    - Set subseq[j] as an empty array
  - Insert subseq[j] into graph[subseq[j - 1]]
Return topologicalSort(graph)

Solve now