Remove Duplicates From Sorted Array II

Python Java C++

def removeDuplicates(nums):
    # k represents position in modified array
    k = 0
    
    # Compare against modified array using k-2
    for i in range(len(nums)):
        if i == 0 or i == 1 or nums[i] > nums[k-2]:
            nums[k] = nums[i]
            k += 1
            
    return k

class Solution {
    // Allows at most two duplicates in final array
    public int removeDuplicates(int[] nums) {
        int k = 0;
        
        for (int i = 0; i < nums.length; i++)
            if (i == 0 || i == 1 || nums[i] > nums[k-2])
                nums[k++] = nums[i];
        
        return k;
    }
}

class Solution {
public:
    int removeDuplicates(vector& nums) {
        // k represents position in modified array
        int k = 0;
        
        for (int i = 0; i < nums.size(); i++)
            if (i == 0 || i == 1 || nums[i] > nums[k-2])
                nums[k++] = nums[i];
        
        return k;
    }
};

Problem Statement

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

Category: Two Pointers | Difficulty: Medium

Detailed Explanation

Approach

This solution uses a single pass approach with a clever comparison against the modified array we're building. Instead of tracking frequencies, we use the fact that the array is sorted and compare each element with the element two positions back in our result array.

Key Concepts

1. Modified Array Comparison: We compare current elements against the modified array (k-2) rather than the original array. This is the key insight that makes the solution elegant.

2. Two Allowed Duplicates: The first two elements (i == 0 || i == 1) are always kept, ensuring we allow up to two occurrences of any number.

3. In-place Modification: We modify the array in-place by overwriting elements at position k.

Algorithm Steps

1. Initialize k as the position in our modified array

2. For each element in the array:

   • Always keep first two elements (i == 0 or i == 1)
   • For other elements, compare with element two positions back in modified array
   • If current element is larger, it's valid to include
   • Copy valid elements to position k and increment k

Visual Example

Input: nums = [1,1,1,2,2,3]

Step by step:
k = 0: [1,1,1,2,2,3] -> [1]       (i=0, first element)
k = 1: [1,1,1,2,2,3] -> [1,1]     (i=1, second element)
k = 2: [1,1,1,2,2,3] -> [1,1,2]   (i=3, 2 > nums[0])
k = 3: [1,1,1,2,2,3] -> [1,1,2,2] (i=4, 2 > nums[1])
k = 4: [1,1,1,2,2,3] -> [1,1,2,2,3] (i=5, 3 > nums[2])

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

Time and Space Complexity

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - In-place modification

Why Compare with k-2?

Comparing with k-2 is crucial because:

1. It looks at the second-to-last element we kept in our result
2. If current element is greater than nums[k-2], it's either:
   • A new number (which we want to keep)
   • A third duplicate (which we want to skip)

Edge Cases

• Array length ≤ 2: Return original length
• All elements same: Return 2
• No duplicates: Return original length
• All elements appear exactly twice: Return original length

Common Mistakes

1. Comparing with original array instead of modified array
2. Not handling first two elements separately
3. Using extra space to count frequencies