# Check whether an Array is subset of another Array

Check whether an Array is subset of another Array” is a basic problem which can be solved using multiple methods like brute-force, sorting, binary search and hashing.

Here, in this problem, we are given two arrays; arr1 and arr2 and our task is to write a program to check whether arr2 is subset of arr1.

Note: There are no repetitions of elements in both the arrays.

```Example:

Input:
Arr1 = {1, 2, 3, 4, 5}
Arr2 = {4, 5}
Output:
Arr2 is subset of Arr1

Input:
Arr1 = {7, 9, 4, 2, 6}
Arr2 = {4, 7, 3}
Output:
Arr2 is not a subset of Arr1```

There are multiple methods to solve this problem. Here, in this post, we will discuss three of them.

Method 1: Brute-Force Approach

The simplest solution to check whether an array is subset of another array is that, for every element of Arr2, traverse Arr1 and check whether element of Arr2 is exists in Arr1 or not.

The time complexity of this solution is O(n*m), where ‘n’ and ‘m’ are size of two arrays.

#### C++ Program to Check whether an Array is subset of another Array is as follows:

```/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;

/* Function to Check whether an Array is subset of another Array  */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;

/* For Every Element of Arr2, linearly search in Arr1 */
for(int i = 0; i < size2; i++)
{
int temp = 0;
for(int j = 0; j < size1; j++)
{
if(Arr2[i] == Arr1[j])
{
temp = 1;
break;
}
}
if(temp == 0)
{
subset = false;
break;
}
}

/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}

int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};

int size1 = sizeof(Arr1)/sizeof(Arr1);
int size2 = sizeof(Arr2)/sizeof(Arr2);

checkSubset(Arr1,Arr2,size1,size2);
}
```
```Output:
Arr2 is subset of Arr1
```

Method 2: Sorting and Binary Search

The steps required to check whether an Array is subset of another Array are as follows:

1. Sort first array; Arr1.
2. Now, for every element of second array, Arr2; search that element in Arr1 using Binary Search.
3. If all the elements of second array are present in first array, then second array is subset of first array. Else, second array is not subset of first array.

The time complexity of this solution would be O(mlogm + nlogm), where ‘n’ and ‘m’ are respective size of array. “mlogm” is for sorting and “nlogm” is for binary search for every element of second array.

#### C++ Program to Check whether an Array is subset of another Array is as follows:

```/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;

/* Function to implement Binary Search */
bool binarySearch(int Arr[], int low, int high, int ele)
{
while(low <= high)
{
int mid = (low + high) / 2;

/* Check if middle element is ele */
if(Arr[mid] == ele)
return true;

/*
If middle element is greater than ele,
then, if ele is present, it must be present
in lower half of array
*/
if(Arr[mid] > ele)
high = mid - 1;

/*
If middle element is smaller than ele,
then, if ele is present, it must be present
in upper half of array
*/
else
low = mid + 1;
}

/* If ele is not present, return false */
return false;
}

/* Function to Check whether an Array is subset of another Array  */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;

/* Sort first Array */
sort(Arr1, Arr1 + size1);

/* For Every Element of Second Array, binary search in first array*/
for(int i = 0; i < size2; i++)
{
subset = binarySearch(Arr1, 0, size1-1, Arr2[i]);
if(subset == false)
{
break;
}
}

/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}

int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};

int size1 = sizeof(Arr1)/sizeof(Arr1);
int size2 = sizeof(Arr2)/sizeof(Arr2);

checkSubset(Arr1,Arr2,size1,size2);
}
```
```Output:
Arr2 is subset of Arr1```

Method 3: Hashing Based Approach

The steps required to check whether an Array is subset of another Array are as follows:

1. Create a Hash set for all the elements of Arr1.
2. Traverse Arr2 and for every element of Arr2, search Hash set.
3. If all elements of Arr2 are present in Hash Set, then Arr2 is subset of Arr2, else, not.

The time complexity of this solution would be O(nlogm), where ‘n’ and ‘m’ are size of arrays and logm for searching in set.

#### C++ Program to Check whether an Array is subset of another Array is as follows:

```/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;

/* Function to Check whether an Array is subset of another Array  */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;

/* Create a Hash Set */
set <int> hashset;

/* Insert All Elements of Arr1 into hashset */
for(int i = 0; i < size1; i++)
{
hashset.insert(Arr1[i]);
}

/* For every Element of Arr2, search in hashset */
for(int i = 0; i < size2; i++)
{
if(hashset.find(Arr2[i]) == hashset.end())
{
subset = false;
break;
}
}

/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}

int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};

int size1 = sizeof(Arr1)/sizeof(Arr1);
int size2 = sizeof(Arr2)/sizeof(Arr2);

checkSubset(Arr1,Arr2,size1,size2);
}

```
```Output:
Arr2 is subset of Arr1
```