# Check Subset

Posted: 2 Oct, 2020

Difficulty: Easy

#### 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

- If the length of ARR2 is greater than ARR1 then return false, as ARR2 can’t be a subset.
- For every element of ARR2, check if it is present in ARR1 or not.
- 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.
- Else, if it is not there, return false.
- If all the elements of ARR2 are found, then return true.

Approach 2

- If the length of ARR2 is greater than ARR1 then return false, as ARR2 can’t be a subset.
- Create a map for storing the frequency of elements of ARR1.
- Iterate array ARR1, and update the frequency of ARR1.
- Now, iterate through ARR2 and check if the current element of ARR2 is in the map or not, it is not in the map then returns false.
- Otherwise, decrease the frequency of the current element by 1 and check if the updated frequency is positive or not, if it is negative then return false.
- If the whole ARR2 is traversed, then return true.

SIMILAR PROBLEMS

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy

# Wildcard Queries

Posted: 31 Jul, 2021

Difficulty: Hard