Remove Duplicates from Sorted Array II · Optimal Solution

Look back two. Allow at most two copies.

A medical lab stores patient samples sorted by identifier, allowing up to two tubes per patient for verification. A write pointer accepts a sample only when the value at write − 2 differs from the incoming one — guaranteeing no identifier appears more than twice. The same one-pass, one-pointer technique from problem 26, with the comparison window widened from 1 to 2. O(n) time. O(1) space.

Interactive

Watch the algorithm run

Concept

Lookback Two Positions

The write pointer starts at 2 (first two elements always kept). For each read position, compare against the value at write − 2. If different, the value can't be a third copy — write it. If equal, it would be a third occurrence — skip it.

Algorithm

Algorithm

The look-back distance is 2 instead of 1. By comparing the current element with the one two positions behind the write pointer, we guarantee at most two copies of any value.

  1. 1

    Initialize write pointer

    Set write = 2. The first two elements are always valid — at most two copies are allowed.

  2. 2

    Scan with read pointer

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

  3. 3

    Copy if allowed

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

  4. 4

    Return count

    After the scan, write equals the count of elements in the valid prefix.

Edge Cases

Edge Patterns

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

Three or more copies

Three consecutive identical values: the third is skipped because it matches nums[write − 2]. Only two copies are kept.

Short array

Arrays with fewer than 3 elements never trigger the scan — they are already valid by definition.

Complexity

Complexity

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