Day 20 : Check Subset

Easy
0/40
Average time to solve is 18m
57 upvotes
Asked in companies
QualcommAmazonMedia.net

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
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.
Constraints:
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
Sample Input 1:
2
4
1 2 4 6
3
1 2 6
5
9 3 6 5
3
1 3 3
Sample Output 1:
true
false
Explanation For Sample Input 1:
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.
Sample Input 2:
2
3
2 3 4
2
4 3
4 
4 4 2 4
4
2 4 5 3
Sample Output 2:
true
false
Hint

Think of searching all the numbers present in the ARR2.

Approaches (2)
Brute Force Approach
  1. If the length of ARR2 is greater than ARR1 then return false, as ARR2 can’t be a subset.
  2. For every element of ARR2, check if it is present in ARR1 or not.
  3. If it is present at index j, then update ARR1[j] to -1, where -1 will tell us that this element of ARR1 has already been matched with some element of ARR2.
  4. Else, if it is not there, return false.
  5. If all the elements of ARR2 are found, then return true.
Time Complexity

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).

Space Complexity

O(1)

 

we are using constant extra space.

Code Solution
(100% EXP penalty)
Day 20 : Check Subset
Full screen
Console