Remove Duplicates from Sorted Array II

medium array two pointers in-place

Problem

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.

Inputnums = [1, 1, 1, 2, 2, 3]

Output5, nums starting [1, 1, 2, 2, 3, …]

Two 1's, two 2's, and one 3 survive. The third 1 is dropped because nums[w-2] is already 1.

nums (sorted, comma-separated)

def remove_duplicates(nums):
    w = 0
    for x in nums:
        if w < 2 or x != nums[w - 2]:
            nums[w] = x
            w += 1
    return w

function removeDuplicates(nums) {
  let w = 0;
  for (const x of nums) {
    if (w < 2 || x !== nums[w - 2]) {
      nums[w++] = x;
    }
  }
  return w;
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int w = 0;
        for (int x : nums) {
            if (w < 2 || x != nums[w - 2]) {
                nums[w++] = x;
            }
        }
        return w;
    }
}

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

Explanation

This is the "each value may stay at most twice" version of duplicate removal, and the whole trick fits in one clever if condition. We keep a write index w that marks how many keepers we have placed so far, and we read every value x once from left to right.

The rule for keeping x is w < 2 || x != nums[w - 2]. The first part lets the first two slots always accept (you can never have "too many" with fewer than two kept). The second part peeks two slots back in the part we already wrote: if x equals nums[w-2], then we have already kept two copies of this value, so we skip it.

Why peeking two back works: because the array is sorted, equal values sit together. If the value two positions before the write head is the same as x, then nums[w-1] is also that value, meaning two copies are already stored.

Example: nums = [1, 1, 1, 2, 2, 3]. The first two 1s are kept (w becomes 2). The third 1 sees nums[0] = 1, equal, so it is dropped. Both 2s are kept, then 3. We end with [1, 1, 2, 2, 3] and return 5.

Everything happens in a single pass with no extra array, so it is fast and uses constant extra memory.

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