This is an extension of problem we have discussed in an earlier post.
I like this problem more because there iss more thinking involved and it forces us to write down the algorithm without using an extra space.
First Hint to solve this problem is how could we utilize the fact that input array is SORTED?
Whenever I see SORTED in a problem statement 'Binary Search' is the first thing that comes to my mind but that won't work in this case because we have to find all the duplicates that exists inside the array so we have to parse all the items inside an array.
Parsing all the items inside an array when array contains 'n' items gives us O(n) time complexity thus defeats the purpose of using Binary Search which is famous of it's logarithm O(logn) time complexity.
Could we utilize the SORTED behavior of the items inside array to get linear time algorithm without using an extra space and without using Binary search?
How about we compare each element with it's neighbor and if they are similar then add them into the list of duplicate elements otherwise insert distinct element back in array.
We are going to use two pointers to solve this, one pointer to compare element and it's neighbor other is to maintain distinct element.
Let's walk through above code with an example-:
Conclusion
We utilized SORTED property of an array by comparing neighboring elements with each other. If it was an unsorted array we had to use extra data-structure like Set and won't be able to do in place algo in linear time.
There are couple of more variation of finding duplicate problem that I want to try and write about in coming days.
Stay tuned. :)
Top comments (6)
I just made an inplace algorithm to move the duplicates replaced with zeros to the end of array, this runs in O(n) time and O(1) space, you can find the code for the same here : codepen.io/karthik19894/pen/XWWwbw...
Try running this array example int[] arr = new int[]{1,2,2,3,4,4,5,6,3, 9, 8, 7,9999}; :D
That is not the correct sample data set for this problem as problem statement specifies that input array must be sorted.
Although I realized that repl was pointing to code base of different problem.I have attached a right code base now.
Yeah I was using repl code example and just changed last element. Was pointing this out because I know some people learning Java will try stuff with the code and be confused about results.
Referring to the example above, wouldn't this give us 4 twice in the duplicates table?
you are right, I should check if item already exists inside the duplicate list. I have updated the code and attached repl.
Thanks for the feedback.