Remove Duplicates from Sorted Array II

Medium

ArrayTwo Pointers

Problem Description

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:


Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2, and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:


Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 7, nums = [0,0,1,1,2,2,3,3,4,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k.

Constraints: - 1 <= nums.length <= 3 * 10^4 - -10^4 <= nums[i] <= 10^4 - nums is sorted in non-decreasing order.

Solution Approaches

Understanding the Problem

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

Before jumping to solutions, let's understand what we're being asked to do:

Key Constraints:

1. The array is already sorted (all duplicates are grouped together) 2. We can modify the array in-place (no extra array allocation) 3. Each unique element can appear at most twice 4. We return the count of valid elements, and they should be in the first k positions

Naive Approach: We could check every element against all previous elements to count occurrences. This would require nested loops with O(n²) time complexity—inefficient!

Key Insight: Since the array is sorted, duplicates are adjacent. We don't need to look at the entire history—we only need to check: "Would adding this element create a third duplicate?"

Solution Code

// Naive approach (inefficient - O(n²))
function removeDuplicatesNaive(nums: number[]): number {
  let k = 0;
  for (let i = 0; i < nums.length; i++) {
    // Count how many times this number already appears
    let count = 0;
    for (let j = 0; j < k; j++) {
      if (nums[j] === nums[i]) count++;
    }
    // Only add if we have less than 2 copies
    if (count < 2) {
      nums[k] = nums[i];
      k++;
    }
  }
  return k;
}

Visualization: RemoveDuplicatesNaiveViz(Component registered but not yet implemented)

Optimal Solution: Two-Pointer Technique

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

The optimal approach uses the Slow-Fast Pointer pattern, also known as the Two-Pointer Technique.

Core Insight:

For any element we're considering adding, we can determine if it would create a third duplicate by comparing it to the element two positions back in our result array.

Why? Because: - If we already placed two copies of a number, the first copy is at position k-2 - If nums[i] === nums[k-2], we already have 2 copies → skip this element - If nums[i] !== nums[k-2], it's safe to add → place at position k

The Algorithm: 1. Handle Edge Case: Arrays with ≤ 2 elements can't violate the "at most twice" rule 2. Initialize Pointers: - k = 2 (write position—where next valid element goes) - i = 2 (read position—start from index 2) 3. Why start at 2? The first two elements are always valid (you need ≥3 occurrences to violate the rule) 4. For each element from index 2 onward: - Check if nums[i] !== nums[k-2] - If true: place nums[i] at position k and increment k - If false: skip this element (don't increment k) 5. Return k (the count of valid elements)

Solution Code

function removeDuplicates(nums: number[]): number {
  // Edge case: arrays with 2 or fewer elements
  if (nums.length <= 2) return nums.length;

  // k is our write pointer (where to place next valid element)
  let k = 2;

  // Read from index 2 onwards
  for (let i = 2; i < nums.length; i++) {
    // Key check: is current element different from element at k-2?
    // If yes, it's safe to add (won't create 3rd duplicate)
    if (nums[i] !== nums[k - 2]) {
      nums[k] = nums[i];
      k++;
    }
    // If nums[i] === nums[k-2], skip (already have 2 copies)
  }

  return k;
}

Visualization: RemoveDuplicatesTwoPointerViz(Component registered but not yet implemented)

Step-by-Step Walkthrough

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

Let's trace the algorithm with nums = [1,1,1,2,2,3]:

Initial State:

- Array: [1,1,1,2,2,3] - k = 2 (write pointer) - i = 2 (read pointer)

Step 1: i=2, k=2 - Current element: nums[2] = 1 - Check: nums[2] !== nums[k-2] → 1 !== nums[0] → 1 !== 1 → false - Action: Skip (don't increment k) - Result: k = 2, i = 3

Step 2: i=3, k=2 - Current element: nums[3] = 2 - Check: nums[3] !== nums[k-2] → 2 !== nums[0] → 2 !== 1 → true - Action: nums[2] = 2, k++ - Array: [1,1,2,2,2,3] - Result: k = 3, i = 4

Step 3: i=4, k=3 - Current element: nums[4] = 2 - Check: nums[4] !== nums[k-2] → 2 !== nums[1] → 2 !== 1 → true - Action: nums[3] = 2, k++ - Array: [1,1,2,2,2,3] - Result: k = 4, i = 5

Step 4: i=5, k=4 - Current element: nums[5] = 3 - Check: nums[5] !== nums[k-2] → 3 !== nums[2] → 3 !== 2 → true - Action: nums[4] = 3, k++ - Array: [1,1,2,2,3,3] - Result: k = 5, i = 6

Loop Ends - Return k = 5 - First 5 elements: [1,1,2,2,3] ✓

Why This Works: The comparison nums[i] !== nums[k-2] elegantly captures: "Do we already have 2 copies of this number in our result?" If the element at k-2 matches the current element, we've already placed two copies (at positions k-2 and k-1), so adding a third would violate our constraint.

Solution Code

// Annotated solution with trace
function removeDuplicates(nums: number[]): number {
  if (nums.length <= 2) return nums.length;

  let k = 2; // Write position starts at 2

  for (let i = 2; i < nums.length; i++) {
    // The magic check: comparing with k-2 position
    // This tells us: "Do we already have 2 copies?"
    if (nums[i] !== nums[k - 2]) {
      // Safe to add - won't create 3rd duplicate
      nums[k] = nums[i];
      k++;
    }
    // Otherwise: already have 2 copies, skip this element
  }

  // k now represents:
  // 1. Position after last valid element
  // 2. Total count of valid elements
  return k;
}

Visualization: RemoveDuplicatesAnimatedViz(Component registered but not yet implemented)