Restore Array

Moderate

0/80

Average time to solve is 25m

10 upvotes

Asked in company

Problem statement

Ninja was having an array ‘NUMS’ of size ‘N’ having unique elements, but due to his fight with Evil, he lost his array.

You are given a 2D array ‘ARR’ of size N - 1 where ARR[ i ]=[ a, b ], indicating that a and b are adjacent in nums array.

Every adjacent pair {a,b} in nums array will exist in ‘ARR’ array as either [a,b] or [b,a].

Help the ninja to restore its num array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains ‘T,’ denoting the number of test cases.

The first line of the test case contains a single integer ‘N’ denoting the size of the ‘NUMS’ array.

The following N - 1 lines contain two space-separated integers denoting the i-th element of ARR[i].

Output Format:

For each test case, print a single line containing 'N' space-separated integers denoting any possible answer array elements.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= ’T’ <= 10
1 <= ‘N’<= 5000
1 <= ARR[i][0], ARR[i][1] <= 10 ^ 6

Where ‘i’ varies from 1 to ‘N’ - 1 and ‘N’ is the length of the array ‘nums’.

Time Limit: 1 sec.

Sample Input 1:

Sample Output 1:

1 2 3 4 6
6 2 3 1

Sample Output Explanation:

First Test case:

If 1 is placed at the first position 
Then the next element will be 2( 2 is adjacent to 1)
After 2, the next element will be 3(1 is taken .hence three will be considered as it adjacent to 2)
After 3 the next element will be 4(2 is already taken. Hence 4 will be considered)
After 4 the next element will be 6(3 is already taken. Hence 6 will be considered)

Thus one of the possible answers is 1 2 3 4 6.

Second Test case:

If 6 is placed at the first position 
Then the next element will be 2( 2 is adjacent to 6)
After 2 the next element will be 3(6 is taken .hence 3 will be considered as it adjacent to 2)
After 3 the next element will be 1(2 is already taken. Hence 1 will be considered)

Thus one of the possible answers is 6 2 3 1.

Sample Input 2:

Sample Output 2:

11 13 15 23
9 22 12 11 14

Hint 1

Make edges between adjacent elements and do the dfs traversal from the vertex with inDegree 1.

Approaches (1)

Approach 1

DFS approach

The main idea is first create edges between adjacent nodes and then do the dfs traversal from the vertex with inDegree 1 as the vertex with inDegree 1 means it has only one adjacent element to it in nums array so it must be present at the first position since the element at the first position has only one element adjacent to it.

Algorithm :

Create edges between adjacent elements from ‘arr’ array and make an adjacency list for this.
Find the node with inDegree 1.
Start the dfs traversal from the node with inDegree 1.
While doing dfs traversal store all the nodes in a list.
After dfs traversal returns the list which stores nodes.

Time Complexity

O(N), where ‘N’ is the size of the array 'NUMS'.

We are doing DFS traversal on the values of the ‘NUMS’ array.

Space Complexity

O(N), where ‘N’ is the size of the array 'NUMS'.

We are creating an adjacency list of the values of the ‘NUMS’ array.

(100% EXP penalty)

Restore Array

Console