text
i = 0
while i < nums.length - 2:
    if nums[i] == nums[i+1] and nums[i] == nums[i+2]:
        remove nums[i+2] (shift all elements left)
        // do not increment i, check same index again
    else:
        i++
return nums.length

Why this fails:

• Space Complexity Violation: Using a Hash Map or a new list requires $O(N)$ space, violating the $O(1)$ constraint.
• Time Complexity: The deletion approach requires shifting elements. In the worst case (e.g., an array of all identical numbers), shifting takes $O(N)$ time for each removal. Doing this for $N$ elements results in $O(N^2)$ time complexity, which may lead to a Time Limit Exceeded (TLE) error on large inputs.

Core Insight for Remove Duplicates from Sorted Array II

The key intuition for the optimal solution lies in the sorted nature of the input. Because the array is sorted, all duplicates are grouped together. We do not need to know the total count of a number; we only need to ensure that for any given number x, we have not already written x twice in our result.

The standard "Remove Duplicates" (LeetCode 26) checks if nums[read] != nums[write - 1]. However, for LeetCode 80, we are allowed two instances. Therefore, the constraint relaxes to checking two positions back.

The Invariant: We maintain a write pointer such that the subarray nums[0...write-1] contains the valid result at all times. When considering a new element at the read pointer, it is valid to include it if it is different from the element at nums[write - 2].

If nums[read] == nums[write - 2], it implies that nums[read] is also equal to nums[write - 1] (due to the sorted property). This would mean adding nums[read] creates a sequence of three identical values. We skip it.

Visual Description: Imagine the array is divided into two parts. The left part (indices 0 to write-1) is the "clean" array. The right part is the unprocessed territory. As the read pointer advances, we look back into the "clean" array at index write-2. If the current value is compatible, we copy it to the write index and expand the clean zone.

Execution Flow

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

1. Initialization:

   • write = 2, read = 2.
   • Current array state: [1, 1, 1, 2, 2, 3] (Indices 0 and 1 are implicitly kept).

2. Iteration 1 (read = 2):

   • Compare nums[read] (value 1) with nums[write - 2] (index 0, value 1).
   • 1 == 1. This is a 3rd duplicate.
   • Action: Skip.
   • State: write remains 2.

3. Iteration 2 (read = 3):

   • Compare nums[read] (value 2) with nums[write - 2] (index 0, value 1).
   • 2 != 1. This is valid.
   • Action: nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 2, 3].
   • Increment write to 3.

4. Iteration 3 (read = 4):

   • Compare nums[read] (value 2) with nums[write - 2] (index 1, value 1).
   • 2 != 1. This is valid.
   • Action: nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 2, 3].
   • Increment write to 4.

5. Iteration 4 (read = 5):

   • Compare nums[read] (value 3) with nums[write - 2] (index 2, value 2).
   • 3 != 2. This is valid.
   • Action: nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 3, 3].
   • Increment write to 5.

6. End:

   • Loop finishes. Return write = 5.
   • The first 5 elements are [1, 1, 2, 2, 3].

Proof of Correctness

The algorithm guarantees correctness through the invariant that nums[0...write-1] always satisfies the problem constraints.

• Base Case: For k=2, the subarray nums[0...1] can contain at most 2 items, which is always valid regardless of values.
• Inductive Step: When adding a new element x at write, we check x != nums[write-2].
  • Since the array is sorted, x >= nums[write-1] >= nums[write-2].
  • If x > nums[write-2], then we cannot have three identical values ending at x. Even if x == nums[write-1], we only have two copies (nums[write-1] and x), which is allowed.
  • If x == nums[write-2], then x == nums[write-1] == nums[write-2], which would form a triplet. By rejecting this case, we prevent any element from appearing more than twice.

Reference Implementation

C++ Solution for LeetCode 80

cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // If the array has 2 or fewer elements, it's already valid.
        if (nums.size() <= 2) {
            return nums.size();
        }

        // 'write' pointer starts at 2 because the first two elements
        // are always allowed in the result.
        int write = 2;

        // 'read' pointer iterates through the rest of the array.
        for (int read = 2; read < nums.size(); read++) {
            // Compare current element with the element two positions back
            // in the VALID part of the array (write - 2).
            if (nums[read] != nums[write - 2]) {
                nums[write] = nums[read];
                write++;
            }
        }

        return write;
    }
};

Java Solution for LeetCode 80

java
class Solution {
    public int removeDuplicates(int[] nums) {
        // Edge case: arrays with length <= 2 require no changes.
        if (nums.length <= 2) {
            return nums.length;
        }

        // Initialize write pointer at 2.
        int write = 2;

        // Iterate with read pointer starting from index 2.
        for (int read = 2; read < nums.length; read++) {
            // If the current number is different from the number
            // located two positions behind in the valid zone, keep it.
            if (nums[read] != nums[write - 2]) {
                nums[write] = nums[read];
                write++;
            }
        }

        return write;
    }
}

Python Solution for LeetCode 80

python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Edge case: small arrays are always valid
        if len(nums) <= 2:
            return len(nums)
        
        # We can always keep the first two elements
        write = 2
        
        # Start reading from the third element
        for read in range(2, len(nums)):
            # Check against the element two positions back in the *result* array
            if nums[read] != nums[write - 2]:
                nums[write] = nums[read]
                write += 1
                
        return write

Q: Why is my output array shorter than expected? Mistake: Resetting the count logic incorrectly or using a separate counter variable that doesn't sync with the write pointer. Explanation: Some candidates try to maintain a count variable for the current number. While possible, it adds complexity (resetting count when number changes). The nums[write-2] check handles this logic implicitly and is less error-prone. Consequence: Correctness fail.