Remove Duplicates from Sorted Array II

Given a sorted integer slice, remove duplicates in-place so that each value appears at most twice. Return the new length k such that the first k elements contain the allowed values in sorted order.

Why this is worth learning

The decision depends on the compacted output, not on a count of the last two input positions. The same argument generalizes to keeping at most k copies.

Before coding: one-minute experiment

Why does comparing nums[read] with nums[read-2] fail on [1,1,1,2,2,2,3] after compaction?

Function signature

func RemoveDuplicatesSortedArrayII(nums []int) int

Inputs / outputs

• nums: sorted slice to modify in-place.
• Return: number of kept elements k; only nums[:k] is valid after the call.

Example

nums = [1,1,1,2,2,3]
After removal: nums = [1,1,2,2,3,_]
Return k = 5

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Because the array is sorted, any value beyond the second occurrence can be skipped. The easiest invariant uses the write index:

Invariant: nums[:write] contains the valid output so far, with no value appearing more than twice.

If write < 2, you can always keep the element. Otherwise, compare nums[read] to nums[write-2]:

• If they are different, the current value has appeared fewer than twice in the output, so keep it.
• If they are the same, this would be a third occurrence - skip it.

Algorithm (step-by-step)

1. If len(nums) <= 2, return len(nums).
2. Set write = 2.
3. For read from 2 to len(nums)-1:
   • If nums[read] != nums[write-2], set nums[write] = nums[read] and increment write.
4. Return write.

Correctness sketch

For length at most two, every value is allowed. Thereafter nums[:w] is the correctly capped prefix of the values already scanned. If the new value equals nums[w-2], sortedness implies the last two kept values both equal it; another copy would violate the cap. If it differs, fewer than two copies of this value are in the kept prefix, so appending is valid. Each accepted value is written no further right than its read position. Induction over the scan establishes the exact sorted prefix and returned length.

Trace (hand walkthrough)

Example input:
nums = [1,1,1,2,2,3]
After removal: nums = [1,1,2,2,3,_]
Return k = 5

Walk:
- start with first two kept: [1,1], write=2
- i=2 val=1, compare nums[write-2]=1 -> skip (would make 3 copies)
- i=3 val=2, compare nums[0]=1 -> keep -> nums[2]=2, write=3
- i=4 val=2, compare nums[1]=1 -> keep -> nums[3]=2, write=4
- i=5 val=3, compare nums[2]=2 -> keep -> nums[4]=3, write=5 => [1,1,2,2,3]

Pitfalls to avoid

• Using the wrong comparison index (the write-2 check is key).
• Failing to handle arrays of length 0, 1, or 2.
• Returning a new slice instead of the new length.

Debugging lens

Trace write separately from read. Use runs of lengths 1, 2, 3, and 5 in the same input so that a mistaken read-2 comparison cannot hide behind uniform runs.

Complexity

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

Implementation notes (Go)

• This approach preserves order and is stable.

Reconstruction checkpoint

Why does comparing nums[read] with nums[read-2] fail on [1,1,1,2,2,2,3] after compaction?

Return to Array & String · Module quiz