Find The Subset Of The Two Arrays

Let's start by understanding the problem of finding a subset of two arrays.

You are given two arrays, your task is to determine which one is the subset of the other using O(n) time complexity.

Hint:

To check whether an array is the subset of the other, we need first to check which of the two arrays has the largest size, the one having the largest size will determine whether the second array with a size less than the larger one is the subset of the first array or not.

Quick Think:

For checking the subset of both arrays, we can make use of the unordered set for storing the numbers in the array with the larger size and then checking the elements of the second array smaller than the size of the first array in the unordered set whether if it’s all elements are present in the unordered set or not if ‘Yes’ then the second array is the subset of the first array else the second array is not the subset of the first array.

Algorithm:

After creating the unordered set, follow the following steps:-

Step1: Insert the array elements into the unordered set one by one.

Step2: Iterate through the second array (whose size is less than the first) and check for the elements in the second array whether it is present in the unordered set or not, if ‘Yes’ then declare the counter variable as the value 1, break the loop and print the result else traverse the loop till the last element and then print the result.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm.

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
/*Function for checking for the second array as (size of first array > size of the second array). */
int firstarraysubset(int firstarr[], int secondarr[], int first, int second)
{
	int firstcount = 0;
	/*Declare the first unordered set. */
	unordered_set<int> firstset;
	/*Insert into the first unordered set. */
	for (int i = 0; i < first; i++)
		firstset.insert(firstarr[i]);
	/*Check for the elements in the unordered set. */
	for (int j = 0; j < second; j++)
	{
		if (firstset.find(secondarr[j]) == firstset.end())
		{
			firstcount = 1;
			break;
		}
	}

	if (firstcount == 1)
		cout << "The second array is not the subset of the first." << endl;
	else
		cout << "The second array is the subset of the first." << endl;
}

/*Function for checking for the first array as (size of first array< size of the second array). */
int secondarraysubset(int secondarr[], int firstarr[], int second, int first)
{
	int secondcount = 0;
	/*Declare the second unordered set. */
	unordered_set<int> secondset;
	/*Insert into the first unordered set. */
	for (int i = 0; i < second; i++)
		secondset.insert(secondarr[i]);
	/*Check for the elements in the unordered set. */
	for (int j = 0; j < first; j++)
	{
		if (secondset.find(firstarr[j]) == secondset.end())
		{
			secondcount = 1;
			break;
		}
	}

	if (secondcount == 1)
		cout << "The first array is not the subset of the second." << endl;
	else
		cout << "The first array is the subset of the second." << endl;
}

/*Driver function to check the above algorithm. */
int main()
{
	int arr1[] = { 11, 1, 13, 21 };

	int arr2[] = { 11, 3, 7, 1, 3, 7 };

	int first = sizeof(arr1) / sizeof(arr1[0]);
	int second = sizeof(arr2) / sizeof(arr2[0]);

	if (first >= second)
		firstarraysubset(arr1, arr2, first, second);
	else if (first < second)
		secondarraysubset(arr2, arr1, second, first);

	getchar();
	return 0;
}

The running time complexity of the above algorithm is: O(n).
The output of the above algorithm is: The first array is not the subset of the second.

Explanation Of The Above Algorithm:

Let us consider the array as given in the algorithm above, as shown in the diagram below

• Now since the size of the second array is greater than the size of the first array so, we will push the elements of the second array into the unordered set as shown in the diagram below.

• Now we will compare the elements of the first array with the elements present in the unordered set and as we can find that all the elements of the first array are present in the unordered set, so we declare the counter variable (secondcount = 1) and print the result i.e., The first array is not the subset of the second.