Author : 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 4 (Check if the given array is subset of another array.) :
Problem: Check if following given array is subset of another array.
Given two arrays, arr1 and arr2, check if arr2 is a subset of arr1. You can assume there are no duplicates in both the arrays.
Example-1:
Input:
arr1 = {2,4,7,1,5}
arr2 = {5,4,2}
Output: arr2 is a subset of arr1
(since all elements of arr2 are present in arr1)
Example-2:
Input:
arr1 = {9,3,1,5}
arr2 = {9,7}
Output: arr2 is not a subset of arr1
(since 7 is not present in arr1)
Approach 1: Brute-Force
For every element of arr2, check whether it is present in arr1 by iterating over it.
Time complexity: O(n • m), where n and m are sizes of arr1 and arr2 respectively.
Space complexity: O(1)
Approach 2: Hashing Approach
The extra work we are doing in naive approach is iterating arr1 every time for each element of arr2. Instead of iterating everytime, we can use a hashset , store all integers from arr1 in the hashset and check directly whether the element is present or not in arr1. We are assuming here that there are no duplicates in the arrays. If duplicates were present, we could have used hashmap instead of hashset. Time complexity of this approach will be O(n+m) and space complexity will be O(n).
Time complexity: O(n+m), as we traverse both array once.
Space complexity: O(n) , as there are only n elements inserted in the hashset so it takes O(n) space .
Piece of code(C++) :-
Java : https://ideone.com/5yLgoG
Python : https://ideone.com/ryeRDP
Approach 3: Improvised Hashing
In the above approach, in order to check whether the element is present in arr1, we have used hashset. Time complexity to for this is O(1) in average, but O(n) in worst case. So the overall time complexity is greater than O(n + m). We can instead use vector<bool> and store true/false at the respective index of element. This approach will perform better compared to approach 2. This approach will work only when array elements are of order less than or equal to 107. We always prefer vector<bool> over array of bools because of internal optimized implementation of vector of bools.
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials