Tuesday, April 15, 2014

Deleting duplicate numbers from a sorted array

Given a sorted array of numbers, how to delete the duplicate numbers in it?

We have to write a function to modify the existing array without using any extra space and return the new length.

The solution to this problem is similar to that of "Deleting all instances of a particular number from a given array".

We have two indices, one which keeps track of the unique elements and the other iterates through all the elements. Each time we visit an element, we check if it matches with the recently added unique elements. If does not match, we add it to the unique elements, otherwise we ignore that element and move on to the next.

This approach runs in O(n) time and O(1) space. Moreover it iterates over the array only once.

Here is the C++ program which implements this.