Remove Duplicates from Sorted Array

EasyTwo pointersLeetCode 26 ↗World 1-14

0:00 / 0:00

Squeeze the duplicates out of a sorted array in place: a read pointer scans ahead while a write pointer keeps each new value.

▼

The problem

LeetCode 26 (Easy). nums is sorted in non-decreasing order. Remove the duplicates in place so each unique value appears once, keeping the order, and return k, the number of unique values; the first k slots must hold them (whatever is after slot k - 1 doesn't matter).

Examples (LeetCode's): [1,1,2] → k = 2, [1,2,_] and [0,0,1,1,1,2,2,3,3,4] → k = 5, [0,1,2,3,4,_,_,_,_,_] (walked through in scene 6; afterwards the array is [0,1,2,3,4,2,2,3,3,4]).

TRY IT ON LEETCODE ▶

The solution

def removeDuplicates(nums):
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

Transcript

Remove Duplicates from Sorted Array. You get a list of numbers, sorted from small to large, and some repeat. Keep one copy of each value, in order, inside the same array, and return k, how many unique values there are. The first k slots must hold them; whatever comes after doesn't matter.

One, one, two gives k equals two: one, two. Zero, zero, one, one, one, two, two, three, three, four gives k equals five: zero through four.

The naive way deletes each repeat and shifts everything after it left. On this list, that's twenty-three moves, and a long run of repeats makes it n squared. A new list is quick, but not in place.

Better: two pointers. Read moves fast, checking every slot. Write moves slow, marking where the next new value goes. Because the list is sorted, repeats sit side by side, so read only compares with the last value kept.

In code, write starts at one. For each read from one, if the value differs from the one just before write, copy it to write and step write. Return write.

Let's walk it. Zero matches zero: skip. One is new: copy it to slot one. The next two ones match: skip. Two is new: slot two. Skip the second two. Three goes to slot three, skip its twin, and four lands in slot four. Write ends at five.

Read passes once: order n time. Just two pointers: order one extra space.

Read fast, write slow, keep the first of each. That's Remove Duplicates from Sorted Array.