LeetCode 26 · Two pointers

Remove Duplicates from Sorted Array, explained with a picture

A reader and a writer on a sorted shelf.

Two pointers
▶ Watch it step by step

The problem

A sorted list may contain duplicates. Remove them in place so each value appears once at the front, and return how many unique values there are.

Input:  [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: 5   (front becomes 0, 1, 2, 3, 4)

Picture it

Picture a reader and a writer on a sorted shelf. The reader looks at every book; whenever it finds a value different from the last one written, the writer puts it in the next slot. Copies sit next to each other, so this catches them all.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two pointers (read, write) on a sorted list. O(n), O(1).

Python solution

def remove_duplicates(nums):
    w = 1
    for r in range(1, len(nums)):
        if nums[r] != nums[w - 1]:
            nums[w] = nums[r]
            w += 1
    return w

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.