Find if an array is a subset of another array in C, C++, Java and Python | faceprep

Find if an array is a subset of another array in C, C++, Java and Python | faceprep

Program to find if an array is a subset of another array is discussed here. If all the elements of array 2 are found in array 1, then array 2 is said to be a subset of array 1.


Find if an array is a subset of another array in C, C++, Java and Python

For example,nnarr1 = {1,2,3,4,5}narr2 = {3,4,5}nnarr2 is a subset of arr1.nnarr3 = {1,2,3,4,5}narr4 = {1,2,9}nnarr4 is not a subset of arr3.n


This problem can be solved in four different ways.

Method 1: An easier approach using two loops. Outer loop to traverse array 1 and an inner loop to check if all the array 2 elements are found in array1.

Method 2: This method uses sorting. The first array is sorted and the binary search is done for each element in array 2.

Method 3: The arrays are sorted and merge type of process is done to check if the array 2 elements are found in array 1.

Method 4: Firstly, the array elements are inserted into a hash table. Secondly, the second array is traversed to check the number of occurrence of each element of array 2 in array 1.


Algorithm to check if an array is a subset of another array

  • Use two loops.
  • Traverse the array using the outer loop.
  • Using the inner loop, check if the elements in array 2 are present in array 1.
  • If all the elements of array 2 are found in array 1, return true.
  • Else, return false.


Find if an array is a subset of another array in C, C++, Java and Python

Program to check if an array is a subset of another array

@@coding::1@@


Time Complexity: O(m*n)


Algorithm using sorting and binary search

  • Sort the array 1 elements.
  • For every element in the array, perform binary search and find if the element is found in the sorted array.
  • If all the elements of the array are found in the sorted array, return true.
  • Else return false.


C++ program to check if an array is a subset of another using sorting and binary search is given below


@@coding::2@@

Time Complexity: O(mLogm + nLogm) if quicksort has the best time complexity of mLogm.

If sorting is done at worst-case, then the time complexity will be O(m^2 + nLogm).



Find if an array is a subset of another array in C, C++, Java and Python

Algorithm using sorting and merging

  • Sort both the arrays.
  • Use Merge type of process to see if all elements of the sorted array are found in sorted array 1.
  • If all the elements of array 2 are found in array 1, return true. Else, return false.

C++ program to check if an array is a subset of another array using sorting and merging is given below .

@@coding::3@@


Time complexity: O(mLogm + nLogn)


Algorithm using hashing

  • Create two hash tables for array 2 and array 1 where the value of the arrays will be stored in column 1 and their the count of each value will be stored in column 2 in the table.
  • Traverse the second array and check the number of occurrence of each element of array 2 in array 1.
  • If the number of occurrences is same, then return true else return false.

C++ program to check if an array is a subset of another using hashing is discussed below

@@coding::4@@


Time Complexity: O(n)


Find if an array is a subset of another array in C, C++, Java and Python

Recommended Programs







Find if an array is a subset of another array in C, C++, Java and Python


c