Remove Duplicates from Sorted Array · Optimal Solution

One write pointer. Unique values compact forward.

A library shelf holds books sorted by catalog number, but over the years duplicates have crept in. An assistant walks the shelf left to right, advancing a write marker only when a new title appears — each unique book slides into the write position while duplicates are simply passed over. After one pass the shelf is compacted: unique titles at the front, the write index reporting how many remain. O(n) time. O(1) space.

Interactive

Watch the algorithm run

Concept

Compare Against Last Written

The write pointer starts at index 1 (the first element is always kept). For each read position, compare against the value at write − 1 — the last confirmed unique. If different, write it and advance; if the same, skip.

Algorithm

Algorithm

The array is sorted, so duplicates are always adjacent. A single forward pass with two pointers compacts unique values to the front.

  1. 1

    Initialize write pointer

    Set write = 1. The first element is always unique, so we start scanning from index 1.

  2. 2

    Scan with read pointer

    For each read from 1 to n − 1, compare nums[read] with nums[write − 1].

  3. 3

    Copy if unique

    If nums[read] ≠ nums[write − 1], copy it to nums[write] and advance write.

  4. 4

    Return count

    After the scan, write equals the number of unique elements.

Edge Cases

Edge Patterns

Understanding boundary behavior is as important as the main algorithm path.

All identical

Every element is the same. The write pointer never advances past 1, producing a single-element result. The read pointer scans the entire array without copying.

Already unique

No duplicates exist. Every comparison succeeds, and the write pointer tracks the read pointer exactly — the array is unchanged.

Complexity

Complexity

Time: O(n) — single pass.
Space: O(1) — two pointers.