Last Updated: 21 Mar, 2021
NINJA’S ARRAY
Moderate
Asked in companies
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 ].
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
Approaches
Algorithm:
- 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.
- If it founds to be true we increment our ‘i’ and search for the next elements in the same way.
- Else we return ‘False’ if the above condition failed.
- 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'.
Algorithm:
- In this approach first, we create a Map to store the indices of the elements of the given array ‘ARR’.
- Now we iterate over each array present in the ‘PIECES’ and for each array, we follow these steps:
- First, try to find out the index of its first element in the array ‘ARR’ from the Map as we stored all the indices in Map.
- Now we have to check if the obtained array is a subarray of the array ‘ARR’ or not starting from the index found before.
- If the subarray is not equal to the array found, we return ‘False’.
- If we are able to traverse the whole array by ‘ARR’ holding the above condition we return ‘True’.