Problem of the day
You are given two integer arrays ARR1 and ARR2 of length N and M respectively. You have to return true if ARR2 is a subset of ARR1, otherwise, return false.
For Example:
If the given arrays are [1, 2, 3] and [1, 2] then you need to return true as ARR2 is a subset of ARR1, but if the given arrays are [1, 2, 3] and [1, 2, 2] then you need to return false since ARR2 is not a subset of ARR1.
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains an integer N representing the length of the first array i.e ARR1.
The second line contains N single space-separated integers representing elements of the array ARR1.
The third line of input contains an integer M representing the length of the second array i.e ARR2.
The fourth line contains M single space-separated integers representing elements of the array ARR2.
Output Format:
For each test case, print "true" if ARR2 is a subset of ARR1, otherwise, print "false".
The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= N <= 10^5
0 <= ARR1[i] <= 10^9
1 <= M <= 10^5
0 <= ARR2[i] <= 10^9
Time Limit: 1 sec
2
4
1 2 4 6
3
1 2 6
5
9 3 6 5
3
1 3 3
true
false
For the first test case:
Here, all the elements of ARR2 are present in ARR1.
For the second test case:
All the elements of ARR2 are not present in ARR1, because there are two 3 in the ARR2 but only a single 3 in ARR1.
2
3
2 3 4
2
4 3
4
4 4 2 4
4
2 4 5 3
true
false
Think of searching all the numbers present in the ARR2.
O(N * M), where N and M are the lengths of the array ARR1 and ARR2 respectively.
In the worst case, we will be searching for every element of ARR2 in ARR1. Searching an element in ARR1 it can take O(N) time, thus total time would be O(N * M).
O(1)
we are using constant extra space.