Find whether an array is subset of another array

Problem Statement

Consider two arrays, array1 and array2. These arrays can contain both positive and negative values, including zero. The array may be unsorted. We need to find whether array2 is the subset of array1 or not, i.e., we need to check if array1 contains all the elements which are available in array2. If array1 contains all the elements which are available in array2, then return 1 else, return 0.

Examples

Example 1:

Input:
Consider two arrays.
array1[] = [10,8,5,61,6,0]
array2[] = [8,6,0,5]
Output: True

Explanation : As array1 contains every element present in array2, which are 8,6,0,5. So, array1 is a subset of array2 .

Example 2:

Input:
Consider two arrays.
array1[] = [15,16,23,2,91,89]
array2[] = [2,76,16]
Output: False

Explanation: Here, array1 has 2,16, which are present in array1, but 76 is not present in array1, so array1 is not a subset of array2.

Approach 1: Naive Approach

Consider the given two arrays and initialize them with array elements. Now, make two loops such that the outer loop picks an element from array2 and goes to the inner loop for searching the value in array1. This process continues till the outer loop reaches the end of array2.

Algorithm:

1. Initialize two arrays, array1, and array2.

2. Outer loop picks an element from array2 and goes into array1.

1. if the value is found, then search for the next value.
2. if the value is not found, then return false.

3. If all the values are found, then return 1.

C++ Code

#include <bits/stdc++.h>
bool subsetchecker(int array1[], int array2[],int len1, int len2)
{
    int i,j;
    i = 0;
    j = 0;
    for (i = 0; i < len2; i++) 
    {
        for (j = 0; j < len1; j++) 
        {
            if (array2[i] == array1[j])
                break;
        }
        if (j == len1)
            return 0; //if value is not found then return 0
    }
    return 1;  // returns 1 if array1 is a subset of array2
}

// Driver code
int main()
{
    int len1,len2;
    int array1[] = { 10,8,5,61,6,0 };
    int array2[] = { 8,6,0,5};

    len1 = sizeof(array1) / sizeof(array1[0]);
    len2 = sizeof(array2) / sizeof(array2[0]);

    if (subsetchecker(array1, array2, len1, len2))
        printf("Array2 is a subset of Array1");
    else
        printf("Array2 is not a subset of Array1");
    getchar();
}

Output

Java Code

class Main{
	static boolean subsetchecker(int array1[],int array2[],int len1, int len2)
	{
	    int i,j;
		i = 0;
		j = 0;
		for (i = 0; i < len2; i++) 
		{
			for (j = 0; j < len1; j++)
			{
				if (array2[i] == array1[j])
					break;
			}
			if (j == len1)
				return false; //if value is not found then return 0
		}
		return true; // returns 1 if array1 is a subset of array2
	}

	// Driver code
	public static void main(String args[])
	{
		int array1[] = { 10,8,5,61,6,0 };
		int array2[] = { 8,6,0,5 };

		int len1 = array1.length;
		int len2 = array2.length;

		if (subsetchecker(array1, array2, len1, len2))
			System.out.print("Array2 is a subset of Array1");
		else
			System.out.print("Array2 is not a subset of Array1");
	}
}

Output

Python Code

def subsetchecker(array1, array2, len1, len2):
    i,j = 0,0
    for i in range(len2):
        for j in range(len1):
            if(array2[i] == array1[j]):
                break
    
        if (j == len1):
            return 0 #if value is not found then return 0
    

    return 1 #returns 1 if array1 is a subset of array2

# Driver code
if __name__ == "__main__":
    
    array1 = [10,8,5,61,6,0]
    array2 = [8,6,0,5]

    len1 = len(array1)
    len2 = len(array2)

    if(subsetchecker(array1, array2, len1, len2)):
        print("Array2 is a subset of Array1 ")
    else:
        print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes O(m*n) time complexity.
• Space Complexity: It takes only O(1) space complexity.

Approach 2: Using Sorting and Binary Search

In this approach, we initially sort the array1 using a sorting technique, and then we pick an element from array2 and then search for the element in the sorted array1. If the element is found in the sorted array1, then we return 1; if the element is not present in the sorted array, then we return 2.

Algorithm

1. Initialize the values in array1 and array2.
2. Use the Quick sort technique to sort the array1.
3. Pick an element from array2 and search for it in sorted array1.
   1. If an element is not found, then return 0.
   2. If all elements are present, then return 1.

C++ Code

#include <bits/stdc++.h>
using namespace std;

void quickSort(int* arr, int si, int ei);
int binarySearch(int arr[], int low,int high, int x);

bool subsetchecker(int array1[], int array2[],int len1, int n)
{
    int i = 0;
    quickSort(array1, 0, len1 - 1);
    for (i = 0; i < n; i++)
      { 
          if (binarySearch(array1, 0, len1 - 1,array2[i])== -1) 
           return 0; 
      } 
     return 1; //All elements are present 
} 
int binarySearch(int arr[], int l,int high, int x) 
  {
   if (high >= l)
    {
        /*low + (high - low)/2;*/
        int mid = (l + high) / 2;

        if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
            return mid;
        else if (x > arr[mid])
            return binarySearch(arr, (mid + 1), high, x);
        else
            return binarySearch(arr, l, (mid - 1), x);
    }
    return -1;
}

void swap(int* a, int* b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

int partition(int Array[], int si, int ei)
{
    int x1 = Array[ei];
    int i = (si - 1);
    int j;

    for (j = si; j <= ei - 1; j++) {
        if (Array[j] <= x1) {
            i++;
            swap(&Array[i], &Array[j]);
        }
    }
    swap(&Array[i + 1], &Array[ei]);
    return (i + 1);
}

void quickSort(int Array[], int si, int ei)
{
    int pi; 
    if (si < ei) {
        pi = partition(Array, si, ei);
        quickSort(Array, si, pi - 1);
        quickSort(Array, pi + 1, ei);
    }
}

/*Driver code */
int main()
{
    int len1,len2;
    int array1[] = {10,8,5,61,6,0};
    int array2[] = {8,6,0,5};

    len1 = sizeof(array1) / sizeof(array1[0]);
    len2 = sizeof(array2) / sizeof(array2[0]);

    if (subsetchecker(array1, array2, len1, len2))
        cout << "Array2 is a subset of Array1";
    else
        cout << "Array2 is not a subset of Array1";
}

Output

Java Code

class Main {
	static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
	{
		int i = 0;
		sort(array1, 0, len1 - 1);
		for (i = 0; i < len2; i++)
                {
                   if (binarySearch(array1,0, len1 - 1,array2[i]) == -1) 
                      return false; 
                }
                return true; //returns 1 if all elements are true 
         } 
         //Binary Search function 
           static int binarySearch(int arr[], int l, int h, int x1) 
           { 
                if (h >= l)
		{
            int mid;
			mid = (l + h)/ 2;
			if ((mid == 0 || x1 > arr[mid - 1]) && (arr[mid] == x1))
				return mid;
			else if (x1 > arr[mid])
				return binarySearch(arr,(mid + 1), h,x1);
			else
				return binarySearch(arr, l,(mid - 1), x1);
		}
		return -1;
	}
	
	static int partition(int arr[], int l, int h)
	{
	    int pivot,i,j;
		 pivot = arr[h];
		 i = (l - 1);
	
		for (j = l; j < h; j++)
		{
			if (arr[j] <= pivot) //if current value is smaller than pivot
			{
				i++;
				int t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		int t;
		t = arr[i + 1];
		arr[i + 1] = arr[h];
		arr[h] = t;

		return i + 1;
	}
	
	static void sort(int arr[], int l, int h)
	{
		if (l < h) 
		{
			
			int pi = partition(arr, l, h);
            sort(arr, l, pi - 1);
			sort(arr, pi + 1, h);
		}
	}

	// Driver Code
	public static void main(String args[])
	{
		int array1[] = { 10,8,5,61,6,0 };
		int array2[] = { 8,6,0,5 };

		int len1 = array1.length;
		int len2 = array2.length;

		if (subsetchecker(array1, array2, len1, len2))
			System.out.print("Array2 is a subset of Array1");
		else
			System.out.print("Array2 is not a subset of Array1");
	}
}

Output

Python Code

def subsetchecker(array1, array2, len1, len2):
	i = 0
	quickSort(array1, 0, len1-1)
	for i in range(len2):
		if (binarySearch(array1, 0, len1 - 1, array2[i]) == -1):
			return 0

	return 1  #all elements are present

def binarySearch(arr, l, h, x1):
	if(h >= l):
		mid = (l + h)//2
		if((mid == 0 or x1 > arr[mid-1]) and (arr[mid] == x1)):
			return mid
		elif(x1 > arr[mid]):
			return binarySearch(arr, (mid + 1), h, x1)
		else:
			return binarySearch(arr, l, (mid - 1), x1)

	return -1


def partition(Array, si, ei):
	x1 = Array[ei]
	i = (si - 1)

	for j in range(si, ei):
		if(Array[j] <= x1):
			i += 1
			Array[i], Array[j] = Array[j], Array[i]
	Array[i + 1], Array[ei] = Array[ei], Array[i + 1]
	return (i + 1)


def quickSort(Array, si, ei):
	# Partitioning index
	if(si < ei):
		pi = partition(Array, si, ei)
		quickSort(Array, si, pi - 1)
		quickSort(Array, pi + 1, ei)


# Driver code
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]

len1 = len(array1)
len2 = len(array2)

if(subsetchecker(array1, array2, len1, len2)):
	print("Array2 is a subset of Array1 ")
else:
	print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes O(m^2) time complexity.
• Space Complexity: It takes O(1) space complexity.

Approach 3: Using Sorting and Merging

In this approach, we sort both arrays in ascending order. Then we compare every array element if the value is not matched, then we return 0 else, we return 1.

Algorithm

1. Initialize two arrays, array1, and array2.
2. Sort array1 in ascending order.
3. Sort array2 in ascending order.
4. Compare every element:
   1. If values are not the same, then return 0.
   2. If all values are matched, then return 1.

C++ Code

#include <bits/stdc++.h>
using namespace std;
bool subsetchecker(int array1[], int array2[],int len1, int len2)
{
	int i = 0, j = 0;
	if (len1 < len2)
		return 0;

	//Sorting the arrays
	sort(array1, array1 + len1);
	sort(array2, array2 + len2);

	while (i < len2 && j < len1)
	{
		
		if (array1[j] < array2[i]) 
                      j++; 
                else if (array1[j] == array2[i]) 
                { 
                     j++;
                     i++; 
                }
                else if (array1[j] > array2[i])
			return 0;
	}

	return (i < len2) ? false : true;
}

// Driver Code
int main()
{
    int len1,len2;
	int array1[] = {10,8,5,61,6,07};
	int array2[] = {8,6,0,5};

	len1 = sizeof(array1) / sizeof(array1[0]);
	len2 = sizeof(array2) / sizeof(array2[0]);

	if (subsetchecker(array1, array2, len1, len2))
		printf("Array2 is a subset of Array1 ");
	else
		printf("Array2 is not a subset of Array1");
}

Output

Java Code

import java.util.Arrays;
class Main
{
	static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
	{
		int i = 0, j = 0;
		if (len1 < len2)
			return false;

		Arrays.sort(array1); // sorts arr1
		Arrays.sort(array2); // sorts arr2

		while (i < len2 && j < len1) 
		{
			if (array1[j] < array2[i]) 
                           j++; 
                        else if (array1[j] == array2[i]) 
                        { 
                           j++;
                           i++;
                        }
                        else if (array1[j] > array2[i])
	                   return false;
		}

		if (i < len2)
			return false;
		else
			return true;
	}

	// Driver Code
	public static void main(String[] args)
	{
	    int len1,len2;
		int array1[] = { 11, 1, 13, 21, 3, 7 };
		int array2[] = { 11, 3, 7, 1 };

		len1 = array1.length;
		len2 = array2.length;

		if (subsetchecker(array1, array2, len1, len2))
			System.out.println("Array2 is a subset of Array1");
		else
			System.out.println("Array2 is not a subset of Array1");
	}
}

Output

Python Code

def subsetchecker(array1, array2, len1, len2):
    i = 0
    j = 0
    if len1 < len2:
        return 0

    array1.sort()
    array2.sort()

    while i < len2 and j < len1:
        if array1[j] < array2[i]:
            j =j+1 
        elif array1[j] == array2[i]:
            j =j+1
            i =i+ 1
        elif array1[j] > array2[i]:
            return 0
    return False if i < len2 else True

# Driver code
array1 = [10,8,5,61,6,0]
array2 = [8,6,0,5]

len1 = len(array1)
len2 = len(array2)
if subsetchecker(array1, array2, len1, len2) == True:
    print("Array2 is a subset of Array1")
else:
    print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes O(n^2) time complexity.
• Space Complexity: It takes only O(1) space complexity.

Approach 4: Use Hashing

In this approach, we create a hashtable and store array 1 into it. Now traverse through every element in the array2 and search for it the hashtable. If the element is not found, then return 0 else, return 1.

Algorithm

1. Initialize two arrays, array1, and array2.
2. Create a hashtable and store all the elements of array1 into it.
3. For every element in array2, search in the hashtable.
   1. If the value is not found, then return 0.
   2. If all values are found, then return 1.

C++ Code

#include <bits/stdc++.h>
using namespace std;
bool subsetchecker(int array1[], int len1,int array2[], int len2)
{
	set <int> hashset;
	
	//hset stores all values
	for (int i = 0; i < len1; i++)
	{
		hashset.insert(array1[i]);
	}
	
	//checking for all values in arr2
	for (int i = 0; i < len2; i++) 
	{
		if (hashset.find(array2[i]) == hashset.end())
			return false;
	}
	return true;
}

// Driver Code
int main()
{
    int len1,len2;
	int array1[] = { 11, 1, 13, 21, 3, 7 };
	int array2[] = { 11, 3, 7, 1 };
	 len1 = sizeof(array1) / sizeof(array1[0]);
	 len2 = sizeof(array2) / sizeof(array2[0]);

	if (subsetchecker(array1, len1, array2, len2))
		cout << "Array2 is a subset of Array1"<< "\n";
	else
		cout << "Array2 is not a subset of Array1"<< "\n";
}

Output

Java Code

import java.util.HashSet;
class Main
{
	static boolean subsetchecker(int array1[],int array2[], int len1,int len2)
	{
		HashSet <Integer> hs = new HashSet<>();

		// to store all values
		for (int i = 0; i < len1; i++) {
			if (!hs.contains(array1[i]))
				hs.add(array1[i]);
		}

		//checking if all values are present
		for (int i = 0; i < len2; i++)
		{
			if (!hs.contains(array2[i]))
				return false;
		}
		return true;
	}
	// Driver Code
	public static void main(String[] args)
	{
	    int len1,len2;
		int array1[] = {10,8,5,61,6,0};
		int array2[] = {8,6,0,5};

		len1 = array1.length;
		len2 = array2.length;

		if (subsetchecker(array1, array2, len1, len2))
			System.out.println("Array2 is a subset of Array1");
		else
			System.out.println("Array2 is not a subset of Array1");
	}
}

Output

Python Code

def subsetchecker(array1, len1, array2, len2):
	
	# STL set for hashing
	hs = set()

	# hset stores all the values of arr1
	for i in range(0, len1):
		hs.add(array1[i])

	# to check if all values are present
	for i in range(0, len2):
		if array2[i] in hs:
			continue
		else:
			return False
	return True

# Driver Code
if __name__ == '__main__':
	
	array1 = [ 10,8,5,61,6,0 ]
	array2 = [ 8,6,0,5 ]
	
	len1 = len(array1)
	len2 = len(array2)
	
	if (subsetchecker(array1, len1, array2, len2)):
		print("Array2 is a subset of Array1")
	else:
		print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes log2n time complexity.
• Space Complexity: It takes O(n) space complexity.

Approach 5:  Using Set

In this approach, we use a set to find if array1 is a subset of array2 or not. First, add all the elements of array1 to the set and save the size of the set in a variable ‘s’, now, insert all the elements of array2 to the same set. If the size of the set is the same as the ‘s’, then return 1 else, return 0.

Algorithm

1. Initialize two arrays, array1, and array2.
2. Copy all the elements of array1 to set.
3. Store the size of the set in a variable.
4. Copy all the elements of array2 to the same set.
5. If (size == set_size):      return 1 else return 0

C++ Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int len1,len2,i;
	int array1[] = { 10,8,5,61,6,0 };
	int array2[] = {8,6,0,5 };
	len1 = sizeof(array1) / sizeof(array1[0]);
	len2 = sizeof(array2) / sizeof(array2[0]);
	unordered_set <int> s1;
	for (i = 0; i < len1; i++) 
	{
		s1.insert(array1[i]);
	}
	int p = s1.size();
	for (i = 0; i < len2; i++) 
	{
		s1.insert(array2[i]);
	}
	if (s1.size() == p) {
	cout << "Array2 is a subset of Array1"<< "\n";
	}
	else {
		cout << "Array2 is not a subset of Array1 "<< "\n";
	}
}

Output

Java Code

import java.io.*;
import java.util.*;

class Main
{
public static void main (String[] args)
{

int len1,len2,s,i;
	int array1[] = {10,8,5,61,6,0};
	int array2[] = {8,6,0,5};
	len1=array1.length;
	len2=array2.length;

	Set <Integer> s1 = new HashSet();
	for ( i = 0; i < len1; i++)
	{
    	s1.add(array1[i]);
	}
    s = s1.size();
	for ( i = 0; i < len2; i++)
	{
	    s1.add(array2[i]);
	}

	if (s1.size() == s)
    	System.out.println("Array2 is a subset of Array1");
	else
    	System.out.println("Array2 is not a subset of Array1" );
}
}

Output

Python Code

array1 = [ 11, 1, 13, 21, 3, 7 ]
array2 = [ 11, 3, 7, 1 ]
len1 = len(array1)
len2 = len(array2)
s = set()
for i in range(len1) :
	s.add(array1[i])

size = len(s)
for i in range(len2) :
	s.add(array2[i])

if (len(s) == size) :
	print("Array2 is a subset of Array1")

else :
	print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes (m+n) time complexity.
• Space Complexity: It takes O(1) space complexity.

Approach 6: Using Frequency Table

In this approach, we create a frequency table for all the elements of array1, and we search for array2 elements' frequency in the frequency table. If the element frequency is not found, then we return 0.

Algorithm

1. Initialize two arrays, array1, and array2.
2. Increase the frequency of every array element in array1.
3. Traverse through array2 and decrease the frequency if the array element is found.
   1. If an element is not found, then return 0.

4. If all the elements are found, then return 1.

C++ Code

#include <bits/stdc++.h>
using namespace std;

bool subsetchecker(int array1[], int len1,int array2[], int len2)
{
	// frequency table using STL
	map<int, int> freq;
	

	for (int i = 0; i < len1; i++)
	{
		freq[array1[i]]++;
	}
	for (int i = 0; i < len2; i++) 
        {
                if (freq[array2[i]] > 0)
			freq[array2[i]]--;
		else
		{
			return false;
		}
	}
	return true;
}

// Driver Code
int main()
{
	int array1[] = { 10,8,5,61,6,0};
	int array2[] = { 8,6,0,5};
	int len1 = sizeof(array1) / sizeof(array1[0]);
	int len2 = sizeof(array2) / sizeof(array2[0]);

	if (subsetchecker(array1, len1, array2, len2))
		cout << "Array2 is a subset of Array1 "<< "\n";
	else
		cout << "Array2 is not a subset of Array1"<< "\n";
}

Output

Java Code

import java.io.*;
import java.util.*;

class Main{

static boolean subsetchecker(int[] array1, int len1,int[] array2, int len2)
{
    int i;
	//Frequency Table using STL
	HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();

	for(i = 0; i < len1; i++)
	{
		freq.put(array1[i],freq.getOrDefault(array1[i], 0) + 1);
	}
	
	
	for(i = 0; i < len2; i++) 
        { 
                if (freq.getOrDefault(array2[i], 0) > 0)freq.put(array2[i],freq.get(array1[i]) - 1);
		else
		{
			return false;
		}
	}
	return true;
}

// Driver Code
public static void main(String[] args)
{
    int len1,len2;
	int[] array1 = { 11, 1, 13, 21, 3, 7 };
	int[] array2 = { 11, 3, 7, 1 };
	
	len1 = array1.length;
	len2 = array2.length;

	if (subsetchecker(array1, len1, array2, len2))
		System.out.println("Array2 is a subset of Array1 ");
	else
		System.out.println("Array2 is not a subset of Array1");
}
}

Output

Python Code

def subsetchecker(array1, len1, array2, len2):
	freq= {} #creates a frequency table

	for i in range(0, len1):
		if array1[i] in freq:
			freq[array1[i]] = freq[array1[i]] + 1
		else:
			freq[array1[i]] = 1


	for i in range(0, len2):
		if (freq[array2[i]] > 0):
			freq[array2[i]] -= 1
		else:
			return False

	return True

# Driver Code
if __name__ == '__main__':
	
	array1 = [10,8,5,61,6,0]
	array2 = [8,6,0,5]
	
	len1 = len(array1)
	len2 = len(array2)

	if (subsetchecker(array1, len1, array2, len2)):
		print("Array2 is a subset of Array1")
	else:
		print("Array2 is not a subset of Array1")

Output

Complexity Analysis

• Time Complexity: It takes O(m*n) time complexity.
• Space Complexity: It takes only O(1) space complexity.

Conclusion

In this article, we discussed how to check if an array is a subset of another array by using the Naive approach, hashtable, set, arrays, and a few other data structures. We have also discussed the algorithm and code in C++, Java, and Python for the approaches. We hope this article helps you to solve the problem and its variants in a better and more efficient way.

Happy Coding!

People are also reading:

• Longest Palindromic Subsequence using Dynamic Programming
• Move all zeros present in an array to the end
• Rearrange an array such that arr[i] = i
• Sort an array in one swap whose two elements are swapped
• Program to Find LCM and HCF of two numbers
• Majority Element
• Write a Program to convert given inches into equivalent yard, and feet
• WAP to Print Square Using * Character
• Find ancestors of a given node in a Binary Tree
• Maximum size square sub-matrices with all 1’s