Check Subset

Posted: 2 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1
  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.
Try Problem