Can you remove duplicates from a sorted array?

Duplicates from a sorted array can be removed. One common and efficient method used to do this is the Two Pointers method.

## Two Pointers Method

The key idea behind this method is to have one pointer ‘fast‘ scan through the array, and another pointer ‘slow‘ move only if we find a number not seen before. By the end of the process, the part in the array before ‘slow‘ will be all the unique elements in the sorted array.

Let’s go through an example to clarify this:

Suppose we have an input array ‘nums‘ sorted in non-decreasing order such as ‘nums = [0,0,1,1,1,2,2,3,3,4]‘

We start with ‘fast‘ and ‘slow‘ pointers, both initialized at the first index of the array.

Here is a step by step guide of how to do it:

1. Compare the element pointed to by ‘fast‘ with the element before ‘slow‘ (since it’s the last confirmed unique element).

2. If they’re different, increment ‘slow‘ and then copy the element at ‘fast‘ into ‘slow‘.

3. Increment ‘fast‘.

4. Repeat the above steps until ‘fast‘ reaches the end of the array.

In the end, ‘slow + 1‘ will be the new length of the array without duplicates.

Below is the corresponding Python code:

def removeDuplicates(nums):
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
            
    return slow + 1

In the sample input array ‘nums = [0,0,1,1,1,2,2,3,3,4]‘, if we run the ‘removeDuplicates‘ function, it will return ‘5‘, and the first five elements of ‘nums‘ will be ‘[0, 1, 2, 3, 4]‘, which are the unique elements.

This algorithm has a time complexity of ‘O(n)‘, where ‘n‘ is the length of the array, and space complexity of ‘O(1)‘ as it operates in-place.