Remove Duplicates from Sorted Array

The pattern behind this problem is the in-place overwrite: instead of shrinking the array to get rid of duplicates, one pointer reads everything while a second pointer compacts the survivors into the front of the same array. That is possible only because the input is sorted — a sorted array gathers every copy of a value into one consecutive run, so when the reading pointer meets a value it has never seen, it has also already met all of that value’s duplicates. The two pointers are really two different questions: the read pointer asks “what is at the frontier of the unread tape?”, and the write pointer answers “is it a new unique, or a repeat?” — with the writer overwriting dead slots instead of deleting, the answer index falls out of the algorithm for free.

Brute Force: Shift and Remove

Time O(n²)Space O(1)

Removing an element from the middle of an array is the expensive primitive: every element after it must shift one slot left. The brute-force approach leans on that primitive directly. Scan the array with one index, and whenever a value repeats its predecessor, physically remove it by shifting the whole tail left and shrinking the logical length; otherwise advance the scan. The scan never walks off the end because each removal shrinks the logical length.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        n = len(nums)          # logical length; shrinks with each removal
        i = 1                  # scan index
        while i < n:
            if nums[i] == nums[i - 1]:
                # Drop nums[i] by shifting everything after it one slot left.
                for j in range(i, n - 1):
                    nums[j] = nums[j + 1]
                n -= 1
            else:
                i += 1
        return n

Note that i only advances on else: after a removal, the element that slid into the vacated slot must itself be checked, so the same index is inspected again.

Why it is quadratic: each removal walks the remaining tail, and an all-duplicate input removes almost everything — with n copies of one value, the first removal shifts n - 1 elements, the next n - 2, and so on, which sums to about n²/2 shifts in the worst case. That is O(n²) time: the same tail gets walked over and over even though every element was only worth one look. Space stays O(1) because the removal happens in place.

Two Pointers: In-Place Overwrite

OptimalTime O(n)Space O(1)

Both pointers start side by side at index 1, because nums[0] is already the first unique: slow is simultaneously the count of keepers so far and the index where the next unique lands. fast walks the array once, and at every stop it compares its value against the last value that was kept — nums[slow - 1]. Equal means fast has found another copy of an already-kept value, so it steps on and nothing is written. Different means fast has found the first element of a brand-new run, so that value overwrites the slot at slow and slow advances. Comparing to the last written value instead of the neighbor is exactly what lets the pointer skim over duplicates and still write each new unique once.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        slow = 1                            # write frontier: nums[0] is kept
        for fast in range(1, len(nums)):
            if nums[fast] == nums[slow - 1]:
                continue                    # duplicate of the last keeper: skip
            nums[slow] = nums[fast]         # new unique: overwrite the frontier
            slow += 1
        return slow                         # count and index collapse into one

Watch the markers on [1, 1, 2]: fast reads the duplicate with slow frozen, then the 2 overwrites the stale slot and k lands on 2.

fast = 1 · 1 equals last written 1 — duplicate

nums — one array, written in place

▲ slow▲ fast

last written: 1slow = 1 — write slot and count of uniques

the read pointer scans every element once; a duplicate is passed with the write frontier frozen, and each new unique overwrites the slot at slow — so the kept prefix always packs left

1 / 3

currentcomparingresultdiscarded

The setup is one sentence: nums[0] = 1 is the first unique by definition, so the write frontier slow = 1 marks the slot where the next unique lands, and it already doubles as the count of kept values. The read pointer fast starts right beside it at index 1, and the very first comparison is already a duplicate: 1 versus the last written 1. A duplicate does nothing — no write, and slow stays frozen while fast moves on.

Watch the full tape [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]: every duplicate run is passed with slow frozen, every new unique overwrites the frontier, and the final k = 5 is exactly where slow ends up.

fast = 1 · 0 equals last written 0 — duplicate

nums — one array, written in place

▲ slow▲ fast

last written: 0slow = 1 — write slot and count of uniques

the read pointer scans every element once; a duplicate is passed with the write frontier frozen, and each new unique overwrites the slot at slow — so the kept prefix always packs left

1 / 9

currentcomparingresultdiscarded

Same opening move as the short trace: the 0 at index 0 is kept, slow = 1 is the first write slot, and fast = 1 immediately reads a duplicate 0. The rhythm for the whole run is now fixed: every read asks one question — is the fast value equal to the last written value? Equal means skip, different means write.

Why it is linear: fast advances once per element, so the read side costs exactly n comparisons, and slow advances once per unique — at most n writes. That is O(n) time with no re-scanning, in dramatic contrast to the shift-based O(n²) brute force that walks the same tail repeatedly. Space is O(1): the overwrites happen on the array itself, and the only other state is two indices. Correctness rests on the sorted order: each new value fast finds is the first of its run, so writing it at the frontier preserves the relative order of the uniques, and skipping the rest of the run never abandons a survivor. An empty-adjacent edge case takes care of itself — if nums holds a single element the loop does not run and slow = 1 is returned. The judge also accepts any tail content because it only reads the first k slots.