Explore
ProGrad Programs
About Us

Edit
Reply




Edit

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

Published on 10 Mar 2020

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.


For example,

arr1 = {1,2,3,4,5}
arr2 = {3,4,5}

arr2 is a subset of arr1.

arr3 = {1,2,3,4,5}
arr4 = {1,2,9}

arr4 is not a subset of arr3.


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.


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


C
C++
Java
Python 3

Output
Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 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


C++

Output
Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1


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).


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 .


C++

Output
Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1


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


C++

Output
Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1


Time Complexity: O(n)


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in