Find whether an array is subset of another array

Posted in

Find whether an array is subset of another array
vinaykhatri

Vinay Khatri
Last updated on December 14, 2024

    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.
    1. 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:

    Leave a Comment on this Post

    0 Comments