Remove Duplicates from Sorted Array II

Problem

You are given an integer array nums sorted in non-decreasing order. Rewrite it in place so that each distinct value appears at most twice, keeping the relative order of the kept elements, and return k — the number of elements kept.

The first k slots of nums must hold the answer; anything beyond index k - 1 is ignored by the judge. You must not allocate a second array; O(1) extra memory is required.

Examples

Example 1

Input:  nums = [1, 1, 1, 2, 2, 3]
Output: 5, nums = [1, 1, 2, 2, 3, _]

The third 1 is dropped; everything else appears at most twice already.

Example 2

Input:  nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

Two of the four 1s are dropped.

Example 3

Input:  nums = [5, 5]
Output: 2, nums = [5, 5]

Exactly two copies is allowed — nothing changes.

Constraints

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.
• O(1) extra space; a single pass is expected.

Think about it first

TL;DR

Read/write two pointers with the nums[write - 2] comparison — O(n) time, O(1) space, one pass.

Approach 1 — Brute force (build a filtered copy)

Ignore the space constraint for a moment: walk the array, copy each value into a new list unless it would be a third consecutive copy, then write the list back.

from typing import List

def removeDuplicates(nums: List[int]) -> int:
    kept: List[int] = []
    for x in nums:
        if len(kept) < 2 or x != kept[-2]:
            kept.append(x)
    nums[: len(kept)] = kept
    return len(kept)

Complexity: O(n) time, O(n) space. The time is fine; the O(n) auxiliary list is what violates the O(1)-space requirement.

Approach 2 — Two pointers with an explicit run counter

The insight: the array is sorted, so equal values form contiguous runs. Track how long the current run is; copy an element forward only while the run length is ≤ 2. The write pointer marks the boundary of the kept prefix.

from typing import List

def removeDuplicates(nums: List[int]) -> int:
    write = 0
    run = 0
    for read in range(len(nums)):
        if read > 0 and nums[read] == nums[read - 1]:
            run += 1
        else:
            run = 1
        if run <= 2:
            nums[write] = nums[read]
            write += 1
    return write

Walkthrough on nums = [1, 1, 1, 2, 2, 3]:

Returns 5 with prefix [1, 1, 2, 2, 3].

Complexity: O(n) time, O(1) space.

Approach 3 — Two pointers, comparing against nums[write - 2]

The insight: the counter is redundant. The kept prefix is itself sorted, so nums[read] would be a third copy exactly when it equals the element two positions back in the output, nums[write - 2]. One comparison replaces the run bookkeeping, and it generalizes to “at most K copies” by comparing with nums[write - K].

from typing import List

def removeDuplicates(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

Walkthrough on nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]:

Returns 7 with prefix [0, 0, 1, 1, 2, 3, 3].

Complexity: O(n) time, O(1) space.

Common pitfalls

• Comparing with nums[read - 2] instead of nums[write - 2]: the test must run against the output prefix; the input side may still contain copies you already skipped, which corrupts the count.
• Forgetting the write < 2 guard: the first two elements are always kept; indexing nums[write - 2] before two writes wraps around in Python (negative index) and silently reads the array’s tail.
• Deleting from the list (nums.pop) — each removal is O(n), degrading to O(n^2), and mutating length while iterating invites index bugs.
• Returning the array instead of k: the judge reads the count from the return value and only the first k slots of nums.

Pattern takeaway

The read/write (slow/fast) two-pointer split is the standard tool for in-place filtering: read visits every element once, write marks the boundary of the answer built so far, and the invariant “everything left of write is final” holds throughout. When the kept prefix stays sorted, membership questions about it reduce to a single comparison at a fixed offset: here nums[write - K] for “at most K copies”.