AlgoMaster Logo

Remove Duplicates from Sorted Array II

Last Updated: March 31, 2026

medium

Understanding the Problem

The array is sorted, and we need to allow each value to appear at most twice. Any third (or fourth, fifth, etc.) occurrence of a value must be removed. The tricky part is doing this in-place: we can't create a new array, and we need to return the count of valid elements.

Since the array is already sorted, all duplicates are grouped together. That's a huge advantage. We don't need a hash map to count frequencies because consecutive equal elements tell us everything. The real question is: how do we decide which elements to keep and which to skip, while overwriting the array in a single pass?

The key observation is that for any element at position i, if it's the same as the element two positions back in our result, then it's a third (or more) duplicate and should be skipped. If it differs from the element two positions back, it's safe to keep.

Key Constraints:

  • 1 <= nums.length <= 3 * 10^4 → With n up to 30,000, O(n^2) would be about 900 million operations, which is borderline. O(n) or O(n log n) is preferred.
  • -10^4 <= nums[i] <= 10^4 → Values fit comfortably in standard integers. The range is small enough that counting-based approaches are feasible, but the in-place requirement makes them unnecessary.
  • nums is sorted in non-decreasing order → This is the biggest hint. Sorting is free, and all duplicates are adjacent. We can use a single pointer to decide what to keep.

Approach 1: Count and Overwrite

Intuition

The most natural approach: walk through the array, count how many times you've seen the current value, and only write it to the result if the count is 2 or less. Since the array is sorted, tracking the count is straightforward: every time the value changes, reset the count to 1.

This approach uses an explicit counter variable, which makes the logic very transparent. You always know exactly how many times the current value has appeared so far.

Algorithm

  1. Initialize writePos = 1 (the first element is always kept) and count = 1 (we've seen the first element once).
  2. Iterate from index 1 to n - 1.
  3. If nums[i] == nums[i - 1], increment count. Otherwise, reset count = 1.
  4. If count <= 2, write nums[i] to nums[writePos] and increment writePos.
  5. Return writePos.

Example Walkthrough

1Initialize: writePos=1, count=1, i=1
0
1
1
writePos
1
i
2
1
3
2
4
2
5
3
1/6

Code

This approach works correctly, but it requires an explicit counter and careful reset logic when values change.

What if we could eliminate the counter entirely by looking back at what we've already written?

Approach 2: Optimal (Compare with Two Positions Back)

Intuition

Instead of counting how many times we've seen a value, just compare the current element to the element two positions back in the result. If nums[i] != nums[writePos - 2], we know it's safe to keep. If they're equal, we already have two copies and this would be a third.

The beauty of this approach is that the first two elements are always safe (you can't have more than 2 duplicates with only 2 elements), so we start writePos at 2 and scan from index 2. No special cases, no counter variable.

Algorithm

  1. If the array has 2 or fewer elements, return its length (nothing to remove).
  2. Initialize writePos = 2 (first two elements are always kept).
  3. Iterate from index 2 to n - 1.
  4. If nums[i] != nums[writePos - 2], write nums[i] to nums[writePos] and increment writePos.
  5. Return writePos.

Example Walkthrough

1Initialize: first 2 elements always valid, writePos=2, i=2
0
1
1
1
2
writePos
1
i
3
2
4
2
5
3
1/6

Code