Remove Duplicates from Sorted Array II

LeetCode 80: Remove Duplicates from Sorted Array II Solution & Explanation

Problem Overview

TL;DR: To solve this problem in O(N) time and O(1) space, use a two-pointer approach where a "write" pointer builds the valid array and a "read" pointer scans for candidates, only copying numbers that are strictly greater than the element located two positions behind the current write index.

The goal of LeetCode 80, titled Remove Duplicates from Sorted Array II, is to modify a sorted integer array in-place so that duplicates appear at most twice. You must return the new length of the modified array. The relative order of elements must remain unchanged, and you cannot use extra space for a new array.

Brute Force Approach for Remove Duplicates from Sorted Array II

A naive approach to solving Remove Duplicates from Sorted Array II might involve using a temporary data structure to count frequencies or shifting elements repeatedly.

1. Frequency Map: Iterate through the array, storing counts in a Hash Map. Create a new result list and fill it based on counts (capped at 2). Finally, copy the result back into nums.
2. Deletion: Iterate through the array. If a triplet of duplicates is found (e.g., nums[i] == nums[i+1] == nums[i+2]), remove the element at i+2 and shift all subsequent elements to the left to fill the gap.

Pseudo-code (Deletion Approach):

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.

Algorithm Strategy: Two Pointer Patterns

1. Handle Edge Cases: If the array length is less than or equal to 2, no removal is needed. Return the length immediately.
2. Initialize Pointers:
   • write: Initialize to 2. We can safely keep the first two elements because even if they are duplicates, they are allowed (maximum 2).
   • read: Initialize to 2. This pointer will scan the rest of the array.
3. Iterate and Overwrite:
   • Loop read from 2 to the end of the array.
   • Check the condition: Is nums[read] different from nums[write - 2]?
   • If yes: The current element is valid. Copy nums[read] to nums[write], then increment write.
   • If no: The current element is a third duplicate. Do nothing (effectively skipping it).
4. Return Result: The value of write represents the new length of the valid subarray.

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.

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern is a fundamental technique for array manipulation questions in interviews.

• LeetCode 26: Remove Duplicates from Sorted Array: The stricter version of this problem (max 1 duplicate). The logic is identical, but you check nums[write - 1].
• LeetCode 27: Remove Element: Uses the same read/write pointer logic to remove all instances of a specific value.
• LeetCode 283: Move Zeroes: Moves all zeros to the end while maintaining order. This is essentially "Remove Element" (removing 0s) followed by filling the rest with 0s.
• LeetCode 75: Sort Colors: A more complex variation (Dutch National Flag problem) using three pointers to partition the array in-place.

Reference Implementation

C++ Solution for LeetCode 80

1class Solution {
2public:
3    int removeDuplicates(vector<int>& nums) {
4        // If the array has 2 or fewer elements, it's already valid.
5        if (nums.size() <= 2) {
6            return nums.size();
7        }
8
9        // 'write' pointer starts at 2 because the first two elements
10        // are always allowed in the result.
11        int write = 2;
12
13        // 'read' pointer iterates through the rest of the array.
14        for (int read = 2; read < nums.size(); read++) {
15            // Compare current element with the element two positions back
16            // in the VALID part of the array (write - 2).
17            if (nums[read] != nums[write - 2]) {
18                nums[write] = nums[read];
19                write++;
20            }
21        }
22
23        return write;
24    }
25};

Java Solution for LeetCode 80

1class Solution {
2    public int removeDuplicates(int[] nums) {
3        // Edge case: arrays with length <= 2 require no changes.
4        if (nums.length <= 2) {
5            return nums.length;
6        }
7
8        // Initialize write pointer at 2.
9        int write = 2;
10
11        // Iterate with read pointer starting from index 2.
12        for (int read = 2; read < nums.length; read++) {
13            // If the current number is different from the number
14            // located two positions behind in the valid zone, keep it.
15            if (nums[read] != nums[write - 2]) {
16                nums[write] = nums[read];
17                write++;
18            }
19        }
20
21        return write;
22    }
23}

Python Solution for LeetCode 80

1class Solution:
2    def removeDuplicates(self, nums: List[int]) -> int:
3        # Edge case: small arrays are always valid
4        if len(nums) <= 2:
5            return len(nums)
6        
7        # We can always keep the first two elements
8        write = 2
9        
10        # Start reading from the third element
11        for read in range(2, len(nums)):
12            # Check against the element two positions back in the *result* array
13            if nums[read] != nums[write - 2]:
14                nums[write] = nums[read]
15                write += 1
16                
17        return write