Delete Duplicates From Sorted Array

Delete Duplicates From Sorted Array 

Problem Statement

Write a program that takes input as a sorted array and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the empty indices.

Problem Solving

• We need to update the array in place.
• Something gives me intuition about iterating from left. 
• Now if I were to iterate from right then on encountering a duplicate I need to move it somewhere on the left but that would mess up the order. 
• I need to keep growing up a subarray of duplicate dump in the left. 
• Can we do something like the partition problem where we swap elements into respective groups. 
• One solution is to keep two iterators one tells which position to write as new elements other iterates through the array on each elements we check in a unordered set whether this elements if found or not if found then we move on else we update the write iterator with value on array_itr and then move on.
• This would require us to build a unordered hash set which can store all unique elements in the array and would cost space theta of n as we store exactly n elements in the set. 
• This idea will actually work with unsorted array too. that means this idea does not use the fact that the array is sorted. 
• Hence a better approach could be to iterate with two iterators like in the previous element but instead of checking each element in the set we iterate till we find a number that is not the last element found and update the write pointer.
• This seems to use the fact that we are bound to find duplicates in order and not random.
• Find Core here.

Learning

• Intuitions can be wrong, infact they can be exactly opposite.
• In case of ordering problems a quick way to find out that your solution is optimal is to check whether your solution works on if the elements we unordered. If so then you are not using the sorted information. Like in this case we achieved a better solution by detecting that our solution is agnostic to whether the given array is sorted.