Author : Kumar K
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials
It is suggested to go through previous hashing tutorials from the above link for better understanding ..
PART 3 (Find frequency of each number in the given array , but numbers can be as large as 1000000000) :
Problem : We are given an array of integers(a[n]) . We are given multiple queries of the form : [x] which means we need to output the frequency of integer 'x' in the array. All numbers inside the array are from range [0,1000000000].
Analysis : Running a loop for each query[O(N)] and finding the frequency is a good idea but not very efficient as it takes O(N*Q) time.
Hashing Method :
So , our given input array 'a' , let it be a[9] = {2,3,3,5,2,5,5,5,5} for example and demonstration purpose. Size of this array is 9.
Let us create a new HashMap 'b' , which stores all numbers from array 'a' in this form {element , frequency } ------- { key , value }
Main Idea : We will store frequency of all integers from array 'a' into HashMap 'b'.
This is the main idea of Hashing , we store the information of array 'a' into HashTable 'b'(HashMap here) which helps solving the problem efficiently. :-)
HashMap looks like this after travelling the array 'a'
What is the meaning of b[3]?
- It will tell us about frequency of 3 in array 'a'.
What is the meaning of b[5]?
- It will tell us about frequency of 5 in array 'a'.
What is the meaning of b[2]?
- It will tell us about frequency of 2 in array 'a'.
Algorithm : We will travel the whole array , say , we encounter , a[i] , lets set , x = a[i] , then lets increment value at key 'x' in hash-map 'b' , by doing this :
x = a[i]
b[x] = b[x] + 1
After the algorithm is performed , this is how the final array and (RR) hash-map looks like :
a[9] = {2,3,3,5,2,5,5,5,5}
b = {
Key Value
2 2
3 2
5 5
}
We , can now clearly see , that b[2] = 2 , b[3] = 2 , b[5] = 5
It means , we have pre-calculated frequencies of all numbers in array 'a' by just running a single for loop. All data is stored inside HashMap 'b'.
Voila!!
Time Complexity : As we are running a single for loop , O(N) time is required , to answer all the queries , we iterate over the queries and answer each one of them in O(1) time as we have all the answers pre calculated :-) So , total time taken : O(N+Q).
Space Complexity : We created an extra hashmap 'b' . There can be atmost "N" elements inserted in this hashmap from array 'a' . So space taken is O(N) by the algorithm.
We can call the hashmap 'b' as hash-table or frequency hashmap in this problem :)
code(C++) :-
Java : - https://ideone.com/F5TYFl
Python :- jdoodle.com/ia/GGI
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials