Author(s) : Simran Khanna , Ved Timbadiya
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials
It is recommended to go through previous hashing tutorials to get a better understanding.
PART 5 (Check if a given array is a subset of another array assuming that duplicate elements can be present in any or both of the given arrays) :
Problem: Check if a given array is a subset of another array. Duplicate elements can be present.
Given two arrays, arr1 and arr2, check if arr2 is a subset of arr1.
Example-1:
Input:
arr1 = {2,4,7,1,5,5}
arr2 = {5,4,2}
Output: arr2 is a subset of arr1
Explanation: All elements of arr2 are present in arr1.
Example-2:
Input:
arr1 = {9,3,1,5,2,1}
arr2 = {9,1,1,1}
Output: arr2 is not a subset of arr1
Explanation: Element 1 is present twice in arr1 and thrice in arr2.
Approach: Hashing Approach
We can create a HashMap and store all the numbers in arr1 as keys and their frequencies as value. Frequency of an element will be the number of times that element occurs in arr1.
Then we can iterate over arr2 and check if that number exists in our hashmap or not. If the element is present in hashmap and the frequency is greater than 0 we simply subtract 1 from the frequency and move further. If that number doesn't exist or it's frequency is 0 then we can return false stating this element doesn't exist in arr1 or its frequency in arr1 is less than its frequency in arr2. If we've iterated over all the elements of arr2 we can then return true.
Where n is the size of arr1 and m is the size of arr2
Time Complexity : O(n+m)
Space Complexity : O(n)
Piece of code(JAVA) :-
Piece of code(C++) :-
Python - https://ideone.com/qmKKgi
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials