Home Practice Programming Find whether a given array is a subset of another array

# Find whether a given array is a subset of another array

We are given two arrays, arr1[] and arr2[], that contains n, m number of distinct elements in unsorted order. We are supposed to find, whether the given array arr2 is a subset of another given array arr1 or not.

Example –

```Input:
arr1[] = {1,6,18,20,3,5,7}
int arr2[] = {18,3,7,6}
Output:
the arr2 is subset of arr1

Input:
arr1[] = {1,6,18,20,3,5,7}
int arr2[] = {8,3,7,6}
Output:
the arr2 is not a subset of arr1```

This problem can be solved using two methods –

1. The Naive Approach. Time complexity – O(N*M)
2. The optimized Approach. Time complexity –  O(MlogM + NlogN)

#### Naive Approach

The naive approach would be comparing each element of the arr2 to each and every element of arr1. This would involve interacting over the N elements of arr1, M number of times, where M is the number of elements in arr2.

Since this approach involves the nested loop, the time complexity of this approach reaches O(N*M).

##### Algorithm
```is_subset(arr1, arr2, n, m)
{
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(arr2[j] == arr1[i])
break;
}

if(j==m)
return false
}
return true
}```

#### Optimized Approach

The optimized and fast approach to solving this problem (of finding whether a given array is a subset of another array) will involve, first sorting both the arrays and then comparing whether the arr2 is a subset of arr1 in O(N+M) time as described below –

1. Initialize both the arrays (arr1, arr2)
2. Sort both the arrays (arr1, arr2).
3. Initialize pointer i, j to the first element of arr1, arr2.
4. If arr1[i] == arr[j], check for next elements by increment both the pointer i,j by 1
5. Else if arr1[i] < arr2[j], increment only the ith pointer.
6. Else, break because this symbolizes, the arr2 is not a subset of arr1.

##### Algorithm
```issubset(arr1, arr2, n, m)
{
sort(arr1, arr1+n);
sort(arr2, arr2+m);

i=0
j=0
while(i<n && j<m)
{
if(arr1[i] == arr2[j]){
i++
j++
}
else if(arr1[i] < arr2[j])
i++
else
break
}

if(j == m)
print("arr2[] is a subset of arr1[]")
else
print("arr2[] is not a subset of arr1[]")

}```
##### Implementation of the above algorithm
```//program to check if array arr1[]
//is subset of second array arr2[]

#include &lt;bits/stdc++.h&gt;
using namespace std;

int issubset(int *arr1, int *arr2, int n, int m)
{
int i,j;

//sort arr1 and arr2. This will take O(nlogn + mlogn) time
sort(arr1, arr1+n);
sort(arr2, arr2+m);

for(i=0, j=0; i&lt;n, j&lt;m; ){

//if elements in both the array are same increment
// pointer for both the array
if(arr1[i] == arr2[j]){
i++;
j++;
}

//if current element of the arr1[] is samller than arr2[]
//the check the next element of array1
else if(arr1[i] &lt; arr2[j])
i++;

//if element of arr1[] is greater than arr2[], then
//arr2[] is not subset of arr1[]
else
break;
}

//all the elements of arr2[] are found in arr1[]
//then j will reach the end of arr2[] size
if(j == m)
cout&lt;&lt;&quot;arr2[] is a subset of arr1[]&quot;&lt;&lt;endl;

else
cout&lt;&lt;&quot;arr2[] is not a subset of arr1[]&quot;&lt;&lt;endl;

return 0;
}

int main()
{
int arr1[] = {1,6,18,20,3,5,7};
int arr2[] = {18,3,7,6};

int n = sizeof(arr1)/sizeof(arr1[0]);
int m = sizeof(arr2)/sizeof(arr2[0]);

issubset(arr1, arr2, n, m);

return 0;
}
```
##### Output
`arr2[] is a subset of arr1[]`

Time Complexity

The run time complexity of the above approach is O(NlogN + MlognM) ≈ O(NlogN), where N is the number of elements in arr1[] and M is the number of elements in arr2[]. This time complexity arose due to the sorting we did in the beginning. The time complexity of the loop we are using for finding whether the arr2 is a subset of arr1 is O(N + M)