Remove Duplicates from Sorted Array II: Allow At Most Two

LeetCode Remove Duplicates from Sorted Array II (problem 80) asks you to modify a sorted array in-place so that each element appears at most twice. You return k, the number of elements that remain, and the first k slots of the array must hold the valid values in sorted order.

The problem

Given nums = [1, 1, 1, 2, 2, 3], produce k = 5 with nums[0..4] = [1, 1, 2, 2, 3]. The third 1 is the only element that gets dropped.

Another example: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3] becomes k = 7 with nums[0..6] = [0, 0, 1, 1, 2, 3, 3]. Each value keeps up to two copies.

This is a step up from Remove Duplicates from Sorted Array (LeetCode 26), which only allows one copy per value. The trick is a small but powerful change to the comparison logic.

Approach: write pointer with lookback

You keep a write pointer that starts at index 2. For every element from index 2 onward, you ask one question: is nums[fast] different from nums[write - 2]?

If yes, the value at fast has appeared fewer than two times in the output so far, so you copy it to nums[write] and advance write. If no, the value already has two copies in the output, so you skip it and only advance fast.

Why compare against nums[write - 2] instead of nums[write - 1]? Because the output region is sorted, so if nums[fast] equals nums[write - 2], then nums[write - 1] must also equal it (three or more copies). Comparing two positions back is the exact check for "already have two."

The first two elements are always safe. A sorted array cannot violate the "at most two" rule with only two elements.

Python solution

def remove_duplicates(nums: list[int]) -> int:
    if len(nums) <= 2:
        return len(nums)

    write = 2
    for fast in range(2, len(nums)):
        if nums[fast] != nums[write - 2]:
            nums[write] = nums[fast]
            write += 1

    return write

Visual walkthrough

Trace through nums = [1, 1, 1, 2, 2, 3]. The write pointer starts at 2 because the first two elements are guaranteed valid. Watch how the lookback comparison to nums[write - 2] decides whether each element gets kept or skipped.

At index 2, the value is 1 and nums[write - 2] is also 1. That means there are already two 1s in the output, so the third copy gets skipped. For the remaining elements, the lookback check finds a different value each time, so they all get written. The final array has five valid elements: [1, 1, 2, 2, 3].

Complexity

The fast pointer visits every element exactly once. The write pointer advances at most k times. No hash maps, no counters, no auxiliary arrays.

The building blocks

This problem decomposes into two reusable bricks.

Generalized read-write pointer

The skeleton is the same one you see in Remove Element and Remove Duplicates I:

write = start
for fast in range(start, len(nums)):
    if should_keep(nums, fast, write):
        nums[write] = nums[fast]
        write += 1
return write

The only thing that changes between problems is the should_keep predicate and where write starts. For "at most one," you compare against nums[write - 1]. For "at most two," you compare against nums[write - 2]. For "at most k," you compare against nums[write - k]. The pointer mechanics stay identical every time.

Lookback comparison

Instead of tracking a count of how many times you have seen the current value, you look back into the already-written output. Because the output is sorted, checking nums[write - 2] tells you whether the current value already occupies two slots. This avoids extra variables and keeps the logic to a single if statement.

The lookback trick generalizes: if the problem says "at most k copies," compare nums[fast] against nums[write - k]. You never need a counter.

Edge cases

• All elements the same: every element past index 1 gets skipped. [5, 5, 5, 5] becomes k = 2, output [5, 5].
• No duplicates at all: every comparison passes, write keeps pace with fast, and you return the original length. [1, 2, 3, 4] stays [1, 2, 3, 4].
• Length 1 or 2: the guard clause returns len(nums) immediately. No iteration needed because one or two elements can never violate "at most two."

From understanding to recall

The algorithm here is compact. That compactness can trick you into thinking you do not need to practice it. But under interview pressure, the details bite: should write start at 2 or 1? Is the comparison against write - 1 or write - 2? Do you return write or write + 1?

These micro-decisions are exactly what spaced repetition locks in. Write the solution from scratch. Trace through [1, 1, 1, 2, 2, 3] by hand and confirm each pointer position. Do it again in two days. Then again in a week. The goal is not memorizing the code. It is internalizing the pattern so that the write pointer, the lookback distance, and the return value all flow from the logic without hesitation.

Once this variant is solid, try generalizing it to "at most k" copies. If you can write that version on demand, you have truly absorbed the pattern.

Related posts

• Remove Duplicates from Sorted Array - The simpler version (LeetCode 26) that allows at most one copy per value, using the same read-write pointer skeleton.
• Remove Element - The foundational read-write pointer problem (LeetCode 27) where you filter out a specific value in-place.