1.
Problem Statement
1.1.
Sample Example
2.
Brute Force Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
4.1.
What is an array in c++?
4.2.
What do you mean by sorted array?
4.3.
What is the time complexity of binary search?
5.
Conclusion
Last Updated: Mar 27, 2024

# Find whether an array is a subset of another array

## Problem Statement

In this problem, we will be given two arrays, and we need to find whether one array is a subset of another array. Note that, both the arrays are not sorted and both the arrays have distinct elements.

### Sample Example

Input:

``````A1[]={22,1,13,19,64}
A2[]={1,64,22}``````

Output:

``A2[] is a subset of A1[] ``

Explanation:

``We see that all elements of A2 are present inside the array A1. Hence one array is a subset of another array``

## Brute Force Approach

The naive approach to this program is very simple.

• Check if each element of A2 is present inside A1.
• If it is the case, return true
• Otherwise return False.

### Implementation in C++

``````// program to find whether an array is a subset of another array
#include <bits/stdc++.h>
using namespace std;

// function to check if A2 is a subset of A1
bool isA2SubsetOfA1(int arr1[], int arr2[], int n, int m){
int i, j; // pointers for iterating over arr1, arr2
for(i=0;i<m;++i){

// check if current element of A2 exists in A1 or not
for(j=0;j<n;++j){
if(arr1[j]==arr2[i])
break;
}

// current element doesn't exist in A1 hence it's not a subset
if(j==n) return false;
}
return true;
}

int main(){
// sizes of the array A1, A2
int n = 5;
int m = 3;

int arr1[n] = {11, 5, 3, 7, 1};
int arr2[m] = {11, 1, 7};

cout<<"A2 is"<<(isA2SubsetOfA1(arr1, arr2, n, m)?"":" not")<<" a subset of A1";
return 0;
}``````

Output:

``A2 is a subset of A1``

#### Complexity Analysis

Time complexity: O(m*n) since for each element it's checking inside entire array A1 if it exists or not

Space complexity: O(1) as no extra space is being used.

## Optimized Approach

In the brute force approach for each element in A2, we need to check inside the whole array A1 for its existence. We need to find some clever way of reducing this check over the entire array A1. What if we sort the array. We can then maintain 2 pointers and travel both arrays simultaneously until all elements in A2 are found. We will definitely improve our time complexity from O(m*n) to O(mlogm + nlogn). But can we improve more. Can we make use of the fact that elements in both the arrays are distinct.

Yes we can use hashing for this. We can hash elements of A1 inside a map and store each element’s frequency. For each element in A2, we can check that if the count of that element in the map is greater than 0 or not. If yes, then we can move to next element by decreasing the frequency in the map. If it;s not the case then we can return false straightaway.

### Implementation in C++

``````// program to find whether an array is a subset of another array
#include <bits/stdc++.h>
using namespace std;

// function to check if A2 is a subset of A1
bool isA2SubsetOfA1(int arr1[], int arr2[], int n, int m){
unordered_map<int, int> mp;

// store frequency of all elements in the unordered_map above
for(int i=0;i<n;++i){
mp[arr1[i]]++;
}

// for each element in A2 check if it's there in the map.
// If yes, then continue and decrement the count in map
// otherwise return false

for(int i=0;i<m;++i){
if(mp[arr2[i]]>0){
mp[arr2[i]]--;
}else{
return false;
}
}

// since all elements are found in A1
return true;
}

int main(){
// sizes of the array A1, A2
int n = 5;
int m = 3;

int arr1[n] = {11, 5, 3, 7, 1};
int arr2[m] = {11, 1, 7};

cout<<"A2 is"<<(isA2SubsetOfA1(arr1, arr2, n, m)?"":" not")<<" a subset of A1";
return 0;
}``````

Output:

``A2 is a subset of A1``

Try and compile by yourself with the help of online C++ Compiler for better understanding.

#### Complexity Analysis

Time complexity: O(m+n) in the average case as we are searching for an element inside the unordered map which takes O(1) time in the average case. Then we are iterating through the array A2.

Space complexity: O(n) as we are storing the frequency of elements in the array A1 inside an unordered map.

Also check out - Inorder Predecessor

### What is an array in c++?

An array is a collection of elements. The data type of elements must be same. Whenever declaring an array, datatype of an array must be declared.

### What do you mean by sorted array?

A sorted array is an array in which each element is sorted in ascending or descending order. Some common types of sorting are quick to sort, bubble sort, merge sort, insert sort, etc.

### What is the time complexity of binary search?

The time complexity of the binary search algorithm is O(logN). Where N is the number of elements we apply the search on.

## Conclusion

In this article, we have discussed how to find if an array is a subset of another array. We have used the c++ language to solve this problem. We have also discussed the time complexity and space complexity of the approach.We hope that this blog has helped you enhance your knowledge regarding program to find whether an array is a subset of another array and if you would like to learn more, check out our articles on c++

Recommended problems -

Also read -  Decimal to Binary c++

Do upvote our blog to help other ninjas grow. Happy Coding!”

Live masterclass