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 <bits/stdc++.h>
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<n, j<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] < 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<<"arr2[] is a subset of arr1[]"<<endl;

	else
		cout<<"arr2[] is not a subset of arr1[]"<<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)