Whenever I prepare for the interviews I start with “Arrays and strings” and then move to Linkedlist, trees and eventually find myself lost in plethora of topics that I don’t know much about like Dynamic programming, Graphs etc.
So here we go again, hopefully I get through most of them this time, more importantly understand better what I know already hence writing here.
Problem: Finding duplicates inside an array?
Solution: Let’s draw a simple example of what is expected in this problem.
What are the concerns and questions I have as soon as I hear/read this problem.
Set or HashTable kind of data structure that comes to my mind for most of the array/strings related problems.
Set-: With set I can store only the item not their occurrence, would that do it?
Let’s see: for each item inside an array add them to set, if item already exists inside an array that means that is a duplicate item so we’ll add it to list. Repeat this for all the items inside an array and return the list at the end.
Why Set/HashTable not list or another array-: Both Set and HashTable stores distinct items inside them and they give us O(1) search time which is the fastest among different data structures. When input array is large constant search runtime can be very vital.
Let’s try writing down a pseudo code.
Time Complexity-: O(n)
Space Complexity-: O(n)
n: number of items inside array.
How to update our algorithm when we only have to check if duplicate exists in an array?
We can change our existing algorithm and instead of filling items inside list when we are iterating over set we'll just return true boolean value if item exists inside set or otherwise.
Similar problems -:
This is the simplest and not the most efficient implementation for finding duplicates. In the next article I plan to work on different version of this problem.
Stay tuned.
Top comments (0)