Remove Duplicates from Sorted Array II

How it works

The cleanest approach uses a single condition: we only write an element if the write position is less than 2 (first two elements always go through) OR the current element differs from the element two positions back in the result. This automatically limits each value to at most two occurrences.

Steps

1. Initialize the write pointer l at 0.
2. Iterate through each element in the array.
3. If l < 2 or the current element differs from nums[l - 2], write it at position l and increment l.
4. Return l as the new length.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Comparing with the Wrong Element

In the optimal two-pointer solution, you should compare nums[i] with nums[l - 2], not with nums[l - 1]. Comparing with l - 1 only checks if the current element differs from the previous one, which doesn't prevent more than two consecutive duplicates. You need to look back two positions to ensure at most two occurrences of any value.

Forgetting the Base Case

Arrays with 2 or fewer elements are already valid (each element can appear at most twice). Some solutions fail to handle these edge cases, leading to index out of bounds errors when checking nums[l - 2] with l < 2. Always either return early for small arrays or use a condition like l < 2 to bypass the comparison.

Modifying the Wrong Position

When using two pointers, the write pointer l should advance only after writing a valid element. A common bug is incrementing l before writing or writing to the wrong index. The pattern should be: check condition, write to nums[l], then increment l. Writing to nums[l++] in languages that support it keeps this atomic.

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 0
        for num in nums:
            if l < 2 or num != nums[l - 2]:
                nums[l] = num
                l += 1
        return l

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 0;
        for (int num : nums) {
            if (l < 2 || num != nums[l - 2]) {
                nums[l] = num;
                l++;
            }
        }
        return l;
    }
};