Find whether an array is a subset of another array

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

Frequently Asked Questions

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 -

• Product Array Puzzle
• Beautiful Array

Also read -  Decimal to Binary c++

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