Find duplicate element in an Array! Part- II
Hashing method
For part one solution using sorting method check here.
In previous article we checked that how we can find duplicate element in our array using sorting technique. In this article we will see how we can optimise our code and reduce the time complexity from O(n log n) to O(n).
2. Using Hashing method
Approach-:
What is Hashing and Hash Table ?A hash table is a data structure which is used to store key-value pairs. Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched. Implementing hash tables is called hashing.
Yeah but how do we implement hashing in our program to find duplicate element?
Let me explain this with a simple example. Your college decided to give a box of goodies to all the students of the final year because everyone got placed from 2021 batch. I know this is far from reality for most of us but there’s nothing in assuming for the sake of understanding an important concept xD. There are 500 students and 500 boxes of goodies. Every student is asked to pick his box of goodies at any time from the HOD’s office. How do you think, will the HOD make sure that each student gets only one box of goodies and not more than that? Obviously, he’ll give 1 box of goodies to the student only in exchange of his/her college unique id so that he can mark it down and prevent giving more box of goodies to him/her(Definitely not something that college wants!)and eventually everyone gets their box of goodies.
Now notice the terms “mark it down” and “prevent giving more” in the above example. That’s exactly how our algorithm for finding duplicate number works.
Algorithm -:
a) Make a Boolean array of the length same as the length of our numbers array.
b) Initially set value of every element in the Boolean array to false.
c) Start a loop and while traversing through it, check if the Boolean value at that index is already true.
d) If the Boolean value at that index is true, we will return the value as it means the value has previously been traversed through in the loop and set true, again we get that value implying that it is duplicate.
e) Set the Boolean value at that index to true.
Code-:
Analysis-:
Time complexity-: O(n)
Space complexity-: O(n)
As we have traversed through the loop only once, the time complexity in worst case is O(n). Wow!! We have improved the time complexity of the algorithm from O(n log n) to O(n). Great improvement. But we have increased the space complexity from O(1) to O(n), because we have to create an array to keep track of element and mark them while traversing.
So is this solution optimal as compared to previous solution using sorting algorithm?
In terms of time ? Yes
In terms of space ? No
OPTIMISE IT !!!!
What if interviewer asks us to further optimise the code and reduce the space complexity to O(1) while maintaining a time complexity of O(n)? Let’s check out how to find out duplicate element using fast and slow pointers!
Stay tuned for future updates!