NINJA’S ARRAY

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
UberAppleAdobe

Problem statement

Ninja developed his own coding platform and he wants all the questions of the array to be uploaded on his platform. Now, he wants to create test cases of problems. But as usual, he uses his own ninja technique for selecting the array and call such arrays as 'Ninja arrays'. He has two arrays one of them has distinct integers (named as ‘ARR’) and another one contains arrays of integers (named as ‘PIECES’). According to him, if it is possible to make ‘ARR’ from ‘PIECES’ then that array is a 'Ninja array'.

Your task is to help Ninja to check whether we can form an array of distinct integers ‘ARR’ from an array of integers arrays ‘PIECES’. If it is possible you should return ‘True’ else return ‘False’.

Example:

Case 1:
Suppose given array of distinct integers ‘ARR' = [10, 35] and array of integers array ‘PIECES' = [ [35], [10] ]. So, we return ‘True’ as we can form such array-like first we concatenate [10], then [35] hence it is possible to make ‘ARR’ from ‘PIECES’.

Case 2:
Suppose if the array of distinct integers ‘ARR' = [ 2, 1, 3 ] and an array of integers array ‘PIECES' = [ [ 1, 2 ], [ 3 ] ]. So we return ‘False’ as we cant form such an array because we can’t change the order of [ 1, 2 ].
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a ‘T’ number of test cases.

The first line of each test case contains an integer ‘N’, which represents the size of the array ‘ARR’.

The second line of each test case contains the ‘N’ space-separated integer of array ‘ARR’.

The third line of each test case contains an integer ‘M’ denoting the number of rows in array ‘PIECES’. Then, ‘M’ lines follow.

Each line contains an integer ‘R' denoting the number of columns in that row and ‘R’ space-separated integers denoting the values of the row.

Output Format:

For each test case, print in a line ‘True’ if it is possible to form else print  ‘False’.

Print the output of each test case 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 <= M <= N <= 1000
1 <= R <= 1000
1 <= ARR[i], PIECES[i][j] <=100    

Time Limit: 1 second

Sample Input 1:

2
3
49 18 16
1
3 16 18 49
4 
91 4 64 78
3
1 78
2 4 64
1 91

Sample Output 1:

False
True

Explanation Of Sample Input 1:

Test Case 1:
According to this test case, ‘ARR’ is [ 49, 18, 16 ] and ‘PIECES’ is [ [ 16, 18, 49 ] ]. So we return ‘False’ because it is not possible to make ‘ARR’ from ‘PIECES’ even though the number matches because we can concatenate different arrays in any order but we cant change the orientation of elements inside the array.

Test Case 2:
According to this test case, ‘ARR’ is [ 91, 4, 64, 78 ] and ‘PIECES’ is [ [ 78 ], [ 4, 64 ], [ 91] ]. So we return ‘True’ as it is possible to make ‘ARR’ from ‘PIECES’ as first we concatenate [ 91 ] then [ 4, 64 ] and in last [ 78 ].

Sample Input 2:

2
1
85 
1
1 85
4
1 3 5 7 
1
4 2 4 6 8

Sample Output 2:

True
False

Explanation Of Sample Input 2:

Test Case 1:
According to this test case, ‘ARR’ is [ 85 ] and ‘PIECES’ is [ [ 85 ] ]. So we return ‘True’ as it is possible to make ‘ARR’ from ‘PIECES’.

Test Case 2:
According to this test case, ‘ARR’ is [ 1, 3, 5, 7 ] and ‘PIECES’ is [ [ 2, 4, 6, 8 ] ]. So we return ‘False’ because it is not possible to make ‘ARR’ from ‘PIECES’.
Hint

Can you traverse both arrays iteratively and get any possible outcomes from them?

Approaches (2)
Brute Force Approach

Algorithm:

 

  1. We have to check each and every element of ‘ARR’ in ‘PIECES’ for this we start traversing our ‘ARR’ and for each element ‘ARR[i]’ we check if there exists an array present in ‘PIECES’ such that it starts from ‘ARR[i]’ or not.
  2. If it founds to be true we increment our ‘i’ and search for the next elements in the same way.
  3. Else we return ‘False’ if the above condition failed.
  4. Now we traverse until ‘i’ becomes equal to ‘N’ size of ‘ARR’ if we are able to traverse the whole array by holding the above condition we return ‘True'.
Time Complexity

O(N*M), Where 'N' and 'M' represent the size of the array 'ARR' and 'PIECES', respectively.

 

Since we are iterating through the ‘ARR’ using a parent loop and inside it, we are using another loop that runs through the array ‘PIECES’ and so the time complexity becomes O(N*M). We are also using another loop (innermost loop) inside the middle loop but that loop is running in the combination of the parent loop as the innermost loop runs till ‘i’ reaches the size of the array ‘ARR’ and in each step ‘i’ is incrementing by ‘1’. Thus, overall time complexity is O(N^2).

Space Complexity

O(1)

 

As we are using constant space.

Code Solution
(100% EXP penalty)
NINJA’S ARRAY
Full screen
Console