Arrays: Find whether an array is subset of another array

Problem Statement:

Given 2 arrays, check if arr2 is a subset of arr1.

Consider all the elements are distinct and both the arrays are not sorted.

We can solve this be number of different ways. Some of the ways that are discussed are:

1. Use 2 loops
2. Sorting and binary search method.

1. Using 2 loops.

In this method, we take 2 loops.

Initialize the outer loop with arr2, and inner loop with arr1.
For each element of outer loop, loop through all the elements from the inner loop and check if that element exist or not.
The time complexity for this approach is O(m*n). Because for every element in “m”, we loop through all the elements in “n”.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  
void is_subset(int arr1[], int arr2[], int m, int n) 
{ 
    int i = 0; 
    int j = 0; 
    for (i = 0; i < n; i++) 
    { 
        for (j = 0; j < m; j++) 
        { 
            if (arr2[i] == arr1[j]) 
                break; 
        } 
        // if the above loop is not broken,
        // it means that the element arr2[i] is not present arr1[]
        if (j == m)
        {
            cout<<"arr2 is not a subset of arr1"<<endl;
        }
    } 

            cout<<"arr2 is a subset of arr1"<<endl;
} 


int main()
{
    int arr1[] ={1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    int arr2[] ={ 6, 7, 8, 9};
    is_subset(arr1, arr2, 10, 4);
}

Output:

arr2 is a subset of arr1

2. Sorting and binary search method.

In this approach, we first sort the arr1.

Then we use binary search to search each element from arr2 in arr1.

Sorting takes O(mLogm) time.
Searching takes O(nLogm) time.

Total will be O(mLogm + nLogm)