AlgoMaster Logo

Remove Duplicates from Sorted Array II

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

The array is sorted, and each value may appear at most twice. Any third (or later) occurrence of a value must be removed. The constraint is doing this in-place: we cannot allocate a second array, and we return the count of valid elements left in the front of nums.

Because the array is sorted, all copies of a value are adjacent. We do not need a hash map to count frequencies, since consecutive equal elements already group the duplicates together. The question is how to decide which elements to keep and which to skip while overwriting the array in a single pass.

One element-level rule covers it: for any element at position i, if it equals the element two positions back in the result we are building, then it would be a third copy and must be skipped. If it differs from the element two positions back, it is safe to keep.

Key Constraints

  • 1 <= nums.length <= 3 * 10^4 → n reaches 30,000, so an O(n^2) double loop would run around 900 million comparisons. A single O(n) pass is the target.
  • -10^4 <= nums[i] <= 10^4 → Values fit in a 32-bit int with no overflow concern.
  • nums is sorted in non-decreasing order → Equal values are adjacent, so a single write pointer can decide what to keep without any auxiliary counting structure.

Approach 1: Count and Overwrite

Intuition

Walk through the array while tracking how many times the current value has appeared in a row, and write an element to the result only when that running count is 2 or less. Because the array is sorted, maintaining the count needs no extra structure: every time the value changes from the previous one, reset the count to 1; otherwise increment it.

The count variable makes the rule explicit, since at every step it holds exactly how many copies of the current value have been seen 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 works in one pass, but it carries a counter and the reset logic that goes with it. The next approach removes both by deriving the same decision from the result already written.

Approach 2: Optimal (Compare with Two Positions Back)

Intuition

Instead of counting, compare the current element to the element two positions back in the result being built. If nums[i] != nums[writePos - 2], the element is safe to keep. If they are equal, the result already holds two copies of that value and this one would be a third.

The first two elements are always safe, since two elements can never form a third duplicate. So writePos starts at 2 and the scan starts at index 2, with no counter and no separate handling for the leading elements.

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