Remove Duplicates from Sorted Array II

The trap is treating duplicate removal as a counting problem. The sharper model is an input stream and a compacted result prefix: read every candidate, then write it only when the prefix can still accept it.

For the Remove Duplicates from Sorted Array II solution, the key rule is:

Keep x if fewer than two values have been written, or if x differs from the value two positions back in the valid prefix.

That gives a stable in-place algorithm with O(n) time and O(1) extra space.

Lock down the judged contract

The input is a non-decreasing sorted integer array. Each value may appear at most twice in the retained result.

The function must:

1. Modify nums in place.
2. Preserve the relative order of retained values.
3. Return the new length k.
4. Leave the correct result in nums[0:k].
5. Use O(1) extra memory.

Anything after index k - 1 is irrelevant. The array does not need to be physically shortened or cleaned up.

For example:

[1, 1, 1, 2, 2, 3]

becomes logically:

k = 5
nums[0:5] = [1, 1, 2, 2, 3]

And:

[0, 0, 1, 1, 1, 1, 2, 3, 3]

becomes:

k = 7
nums[0:7] = [0, 0, 1, 1, 2, 3, 3]

The neighboring one-copy duplicate-removal problem uses the same general compaction idea. The difference is the invariant. Keeping one copy compares against the previous retained value; keeping two copies compares against the value two positions back.

That small change is the whole problem.

Recognize the read/write compaction pattern

Two structural facts point directly to two pointers:

• The array is sorted, so equal values are adjacent.
• The result must be built inside the original array.

A frequency map could count values, but it spends extra memory and separates counting from placement. Repeated deletion or shifting can also preserve the result, but it repeatedly moves data that a single forward pass can compact once.

Use two logical positions:

• read: consumes candidates from the original input stream.
• write: marks the next slot in the valid result prefix.

The read position moves through every input element. The write position advances only when a candidate is accepted.

This is two-pointer array compaction. It is not Fast and Slow Pointers, where the pointers move at different rates through a structure, and it is not Sliding Window, where the pointers define a maintained contiguous range. Here, one pointer reads and the other builds a stable prefix.

Think of the array as a conveyor belt. The read pointer inspects every item. The write pointer packs only acceptable items into the front.

Derive the two-back rule

The first two candidates are always safe. A value cannot appear three times in a prefix containing fewer than two elements.

After that, consider a candidate x.

Suppose write is the length of the valid prefix so far. The value at:

nums[write - 2]

is the value two positions back in that prefix.

The acceptance rule is:

write < 2 or x != nums[write - 2]

Why does this enforce the limit?

• If write < 2, the valid prefix has room to accept another value.
• If x == nums[write - 2], the valid prefix already contains two retained copies of x at its end. Writing x would create a third copy.
• If x != nums[write - 2], appending x cannot create three equal retained values.

The important detail is that the comparison uses the result being built, not an untouched portion of the original array.

Invariant: After processing the input candidates seen so far, nums[0:write] contains exactly the retained values from those candidates, in their original relative order, with no value appearing more than twice.

Once you have this invariant, the code becomes mechanical. The difficult part is deciding what write means and what the two-back comparison proves.

Prove the invariant

A short induction argument is enough for an interview.

Initialization

Before processing any input, write = 0, so the valid prefix is empty and correct.

The first candidate is accepted because write < 2. The second candidate is also accepted for the same reason. A prefix of length zero or one cannot violate the at-most-two rule.

Maintenance

Assume the invariant holds before processing candidate x.

There are two cases.

The candidate is rejected

If:

x == nums[write - 2]

then the value two positions back in the valid prefix is x.

Because the input is sorted and the retained prefix preserves input order, the value immediately before x in the prefix is also x. The prefix already ends with two copies of x, so rejecting the candidate prevents a third copy.

The valid prefix remains unchanged and therefore remains correct.

The candidate is accepted

If:

write < 2 or x != nums[write - 2]

then writing x at nums[write] preserves the order in which accepted candidates appeared.

For write < 2, there are not yet enough earlier elements to form three copies.

For write >= 2, x differs from the value two positions back. Since the prefix is sorted, appending x cannot produce three equal copies at the end. All earlier values already satisfied the invariant.

So the enlarged prefix is still correct.

Termination

When the read scan finishes, every input candidate has been classified. The invariant says that nums[0:write] contains exactly the retained values in the correct order.

Therefore, returning write satisfies the judge contract.

Sortedness is essential here. Without it, equal values could be separated by other values, and comparing with the two-back position would not reliably tell us how many copies of x are already in the retained result.

Trace the pointers

Trace the input:

[1, 1, 1, 2, 2, 3]

Here, write is shown before processing each candidate.

Read index	Candidate	write before	Decision	Valid prefix after
0	1	0	Accept: fewer than two written	[1]
1	1	1	Accept: fewer than two written	[1, 1]
2	1	2	Skip: equals nums[0]	[1, 1]
3	2	2	Accept: differs from nums[0]	[1, 1, 2]
4	2	3	Accept: differs from nums[1]	[1, 1, 2, 2]
5	3	4	Accept: differs from nums[2]	[1, 1, 2, 2, 3]

Notice what happens after the third 1 is skipped. Later accepted values overwrite positions that no longer matter.

After processing the candidate 2 at read index 3, the assignment writes it into index 2:

[1, 1, 2, 2, 2, 3]

The final 2 at index 4 is still unread at that moment. The write pointer never moves ahead of the read pointer, so the algorithm does not destroy future input.

Short arrays are handled by the same guard:

• [] returns 0 defensively.
• [5] accepts 5 and returns 1.
• [5, 5] accepts both and returns 2.

The expression nums[write - 2] is evaluated only when write >= 2, so it never uses a negative index.

Implement it in Python

def remove_duplicates(nums: list[int]) -> int:
    write = 0

    for x in nums:
        if write < 2 or x != nums[write - 2]:
            nums[write] = x
            write += 1

    return write

The variables map directly to the problem obligations:

• x is the current candidate from the read stream.
• write is the length of the valid compacted prefix.
• nums[write - 2] is the allowance check: the candidate must differ from the value two positions back.

Python's for x in nums loop continues reading the list from left to right while the function writes only to an earlier position or to the current position. Since write <= read_index throughout the scan, unread input remains intact.

For example, when the third 1 is rejected, write stays at 2. When the next value 2 is accepted, it is written at index 2, which is behind the current read position. The stream keeps moving; the prefix gets denser.

A common bug is to start with write = 2 unconditionally:

write = 2

That fails on empty or one-element arrays unless you add a separate early return. Starting at zero with the guard keeps the boundary logic in one place.

Another tempting comparison is:

x != nums[write - 1]

That allows only one copy of each value. It solves the neighboring one-copy problem, not this one.

Comparing with nums[read - 1] can work in a different count-based design, but it ties the decision to the original stream and requires separate frequency state. The two-back rule is cleaner because it derives the count directly from the prefix we promise to return.

Complexity and edge cases

The algorithm performs one read per input element. Each element is written at most once, and each write advances write by one. There is no nested scan and no repeated shifting.

Therefore:

• Time: O(n)
• Extra space: O(1)

The input array itself is modified, but the algorithm uses only a pointer and scalar values beyond that storage.

Test cases should target the assumptions that make the invariant work:

[7]                         -> [7], k = 1
[7, 7]                      -> [7, 7], k = 2
[7, 7, 7, 7]                -> [7, 7], k = 2
[-3, -3, -2, -1, -1]        -> [-3, -3, -2, -1, -1], k = 5
[1, 2, 3, 4]                -> [1, 2, 3, 4], k = 4
[0, 0, 0, 1, 1, 1, 2]       -> [0, 0, 1, 1, 2], k = 5

Check two things separately:

1. Is k correct?
2. Does nums[0:k] contain the correct stable prefix?

Do not waste effort checking the suffix. The contract explicitly makes it irrelevant.

The transferable recognition rule is this:

When sorted input must be compacted into a stable prefix and each value has a fixed small allowance, define the read stream, define the write prefix, then compare the candidate with the corresponding allowance-th position back in the result.

For “at most twice,” that position is two places back. State the invariant before coding. Once the prefix has a precise meaning, the pointers have nowhere mysterious left to go.