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,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.
@@coding::1@@
Time Complexity: O(m*n)
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).
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)
C++ program to check if an array is a subset of another using hashing is discussed below
@@coding::4@@
Time Complexity: O(n)
Recommended Programs