Remove Duplicates from Sorted Array II

1. Define the problem

Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in place such that each unique element appears at most twice . The relative order of the elements should be kept the same. Return k, the number of elements after removing the duplicates. It does not matter what you leave beyond the first k elements. Use slow and fast pointers , comparing each candidate value against the element two positions back from slow — if they differ, the candidate is still allowed and gets written in.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-10⁴ ≤ nums_i ≤ 10⁴
nums is sorted in non-decreasing order.

Example

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

Outputk = 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.

2. Visualize the solution

Slow and fast pointers, keeping at most two of each value

Statusskip

slow=2, fast=2. nums[fast]=1 equals nums[slow-2]=nums[0]=1 — already two 1s placed, skip and advance fast only.

What happens in this step

slow = 2, fast = 2
nums[fast] = nums[2] = 1
nums[slow - 2] = nums[0] = 1

nums[fast] equals nums[slow - 2], so two 1s are already placed. The candidate is skipped: fast advances to 3, slow stays at 2.

Step 1 of 5

Steps to visualize

Keep the first two elements as-is, since any pair is always allowed.
Point fast at index 2 and slow at the next position to write.
Compare nums_fast against the element two positions back from slow.
If they differ, the candidate is still allowed: write it at slow and advance slow.
If they match, there are already two of this value in place, so skip it and only advance fast.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Slow and fast pointers, keeping at most two of each value

Statusskip

slow=2, fast=2. nums[fast]=1 equals nums[slow-2]=nums[0]=1 — already two 1s placed, skip and advance fast only.

What happens in this step

slow = 2, fast = 2
nums[fast] = nums[2] = 1
nums[slow - 2] = nums[0] = 1

nums[fast] equals nums[slow - 2], so two 1s are already placed. The candidate is skipped: fast advances to 3, slow stays at 2.

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function removeDuplicates(nums) {
  if (nums.length <= 2) {
    return nums.slice();
  }

  let slow = 2;

  for (let fast = 2; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow - 2]) {
      nums[slow] = nums[fast];
      slow++;
    }
  }

  return nums.slice(0, slow);
}

Time: O(n)
Space: O(1) (in place, excluding the returned copy)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 1, 1, 2, 2, 3]`	`[1, 1, 2, 2, 3]`	example from the docstring
`nums = [1, 1, 1, 1, 1]`	`[1, 1]`	more than two occurrences of a single value
`nums = [1, 2, 3, 4]`	`[1, 2, 3, 4]`	no value appears more than twice, so nothing is removed
`nums = [1, 1]`	`[1, 1]`	array shorter than three elements is returned unchanged
`nums = [5]`	`[5]`	smallest valid input: a single element
`nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]`	`[0, 0, 1, 1, 2, 3, 3]`	several distinct values, one of which repeats more than twice

Remove Duplicates from Sorted Array II