Two Pointer

Problem Statement

Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in place return the length of the subarray that has no duplicate in it.

Example 1:

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].

Example 2:

Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after removing the duplicates will be [2, 11]

So how do we solve this ? Let's put our thinking caps on! ......

After thinking for a while, you might find a solution where you use a two-pointer and just count the repeated elements. Which gives you the answer.

def remove_duplicates(arr):
    duplicates = 0

    for pointer_start in range(1, len(arr)):
        pointer_end = pointer_start - 1
        if arr[pointer_start] == arr[pointer_end]:
            duplicates += 1
    return len(arr) - duplicates


print(remove_duplicates([2, 3, 3, 3, 6, 9, 9]))
print(remove_duplicates([2, 2, 2, 11]))

Output:

4
2

But We should not forget the given condition

You should remove all duplicates from the array ! Now one might ask that the arrays are immutable. I understand your confusion, Array size is immutable not the array itself. So we can manipulate the data once created not the size !.

So how should one solve this ?

This is a very good explanation I found online. What are we doing is we are taking two pointers

1. Next
2. nextNonDuplicate

We traverse two pointers just as shown in the image.

def remove_duplicates(arr):
  # index of the next non-duplicate element
  next_non_duplicate = 1

  i = 1
  while(i < len(arr)):
    if arr[next_non_duplicate - 1] != arr[i]:
      arr[next_non_duplicate] = arr[i]
      next_non_duplicate += 1
    i += 1
  return next_non_duplicate