Remove Duplicates from Sorted Array II

Problem Statement

Given a sorted array nums, remove duplicates in place so that each unique value appears at most twice. Return the new length k; the first k elements must hold the result.

Example

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

Two Pointer Approach

Use a slow write pointer. For each value, keep it if we have written fewer than two slots, or if it is greater than the element at slow - 2. Because the array is sorted, that single check enforces the "at most twice" rule.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def removeDuplicates(nums):
    slow = 0
    for num in nums:
        if slow < 2 or num > nums[slow - 2]:
            nums[slow] = num
            slow += 1
    return slow

Java

int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int num : nums) {
        if (slow < 2 || num > nums[slow - 2]) nums[slow++] = num;
    }
    return slow;
}

C++

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

Key Takeaways

• The nums[slow - 2] check is the generalisation of the "keep at most k" trick.
• Change the constant from 2 to k to allow k copies.
• Only works because the input is sorted.