Remove Duplicates from Sorted Array II

Practice Link

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place so that each unique element appears at most twice. Return k — the count of remaining elements — after placing the result in the first k slots of nums.

This is the follow-up to Remove Duplicates from Sorted Array (LeetCode 26), where each element could appear at most once. The only change is the allowed count: 1 → 2.

Intuition#

The approach that works for "at most once" generalises directly to "at most twice" — and to "at most k times" for any k.

Maintain a write pointer j that tracks where the next kept element should land. Scan with a read pointer i from index 1 onward. At each step:

• Count consecutive occurrences of nums[i] by tracking a count variable.
• When you move to a new value, reset count to 1.
• If count ≤ 2, write nums[i] at nums[j] and advance both i and j.
• If count > 2, just advance i — the duplicate is discarded.

Because the array is sorted, all copies of a value are adjacent, so the count resets exactly when the value changes.

Why the write pointer never overtakes the read pointer: j advances at most as fast as i (it skips duplicates beyond the allowed count), so nums[j] = nums[i] is always safe — we're writing to a position we've already read from.

Examples#

Example 1

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

Trace:
i=1: nums[1]==nums[0] → count=2 ≤ 2, keep → j=2
i=2: nums[2]==nums[1] → count=3 > 2, skip
i=3: new value 2     → count=1,   keep → j=3
i=4: nums[4]==nums[3] → count=2 ≤ 2, keep → j=4
i=5: new value 3     → count=1,   keep → j=5
Result: [1, 1, 2, 2, 3]

Example 2

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

i=1: 0==0 → count=2, keep
i=2: 1≠0  → count=1, keep
i=3: 1==1 → count=2, keep
i=4: 1==1 → count=3, skip
i=5: 1==1 → count=4, skip
i=6: 2≠1  → count=1, keep
i=7: 3≠2  → count=1, keep
i=8: 3==3 → count=2, keep
Result: [0, 0, 1, 1, 2, 3, 3]

Solution#

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 1, j = 1, count = 1;
        while (i < nums.size()) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count > 2) {
                    i++;
                    continue;
                }
            } else {
                count = 1;
            }

            nums[j] = nums[i];
            i++;
            j++;
        }

        nums.resize(j);
        return j;
    }
};

Time Complexity: O(n) — single pass through the array.
Space Complexity: O(1) — no extra allocation; modifies in-place.

Why this generalises#

To allow at most k occurrences instead of 2, change the single constant > 2 to > k:

if (count > k) { i++; continue; }

Everything else stays identical — the same write/read pointer dance works for any k ≥ 1.

Follow-up#

Consider: What if the array were not sorted, but you still had to allow at most two occurrences of each value in-place? The count trick breaks because duplicates are no longer adjacent.

One approach: use a hash map to track how many times each value has been written, then apply the same write-pointer pattern. This runs in O(n) time but uses O(n) space — the sorted-array version's O(1) space comes entirely from the "duplicates are adjacent" invariant.