← DSA Atlas
Dedicated problem page · #80

Remove Duplicates from Sorted Array II

MediumTwo PointersSlow write pointer with a keep-at-most-two ruleTwo pointers (in-place compaction)
Solve on LeetCode ↗
80
MediumTwo PointersTwo pointers (in-place compaction)Slow write pointer with a keep-at-most-two rule

Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place so that each unique element appears at most twice. The relative order must be kept. Return k, the number of retained elements; the first k slots of nums must hold the final result, and what remains beyond k does not matter.

Open official problem prompt ↗
In plain English

Compact a sorted array so that no value appears more than twice, reporting how many elements remain.

Picture it like this

Restocking a shelf where the policy allows at most two of any item facing forward: as you slide items left to fill gaps, you refuse to place a third identical can next to the two already there.

Example
Input
nums = [1, 1, 1, 2, 2, 3]
Output
5, with nums starting [1, 1, 2, 2, 3, _]
Why
The third 1 is dropped; every value now appears at most twice, leaving 5 elements.
Constraints
1 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^4nums is sorted in non-decreasing order
Pattern lesson

See the pattern, then code

Slow write pointer with a keep-at-most-two rule
Recognition clue

In-place removal from a sorted array with an 'appears at most twice' cap points to a write pointer that compares against the value two slots back.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Because the array is sorted, a candidate x is legal only if it differs from the element two positions earlier in the output — that guarantees no more than two copies of any value survive.

New words, made simpleKnow these before the algorithm
Write pointer
An index k marking the next slot where an accepted element will be stored.
Compaction
Overwriting kept elements into the front of the array so the useful data is contiguous.
Look-back check
Comparing a candidate against nums[k-2] to enforce the two-copy limit.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Extra array with a counter

Works but violates the in-place, O(1) space expectation.

Copy elements into a fresh list, tracking how many times the current value has been added, then write back.

Time O(n)Space O(n)
Best choiceWrite pointer with nums[k-2] comparison

Single pass, constant space, and generalizes cleanly to 'at most m copies'.

Overwrite in place, accepting a value only when it differs from the element two write-slots earlier.

Time O(n)Space O(1)
The rule we keep true

Invariant

The prefix nums[0:k] always holds a valid compacted result in which every value appears at most twice, in original order.

Why this is correct

Reasoning

Because the input is sorted, all copies of a value are contiguous. If nums[k-2] already equals the candidate, then nums[k-2] and nums[k-1] are two copies of it, so accepting a third would break the cap; rejecting it keeps exactly two. When the candidate differs, at most one copy is at nums[k-1], so it is safe to keep.

The algorithm in three movesSay these aloud before coding
1Keep a write index k starting at 0

k=2 after two 1s, next x=1 equals nums[0] -> skip

2Scan every value x in nums

x=2 differs from nums[0]=1 -> write nums[2]=2, k=3

3Accept x if k < 2 (first two slots always fit) or x differs from nums[k-2]

final k=5, nums=[1,1,2,2,3,...]

4When accepted, write x to nums[k] and increment k

5Return k

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
11
12
23
24
35
1 · Readfirst element
2 · Askk<2?
3 · Update statek=0
4 · ResultAccept, nums[0]=1, k=1
Key takeaway

The third 1 (index 2) is rejected because it equals the value two write-slots back.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Initialize the write pointer

    k counts how many elements have been kept and points at the next write slot.

  2. 2
    Lines 4Scan every element

    Reading x directly by value keeps the read pointer implicit in the for-loop.

  3. 3
    Lines 5The acceptance test

    k < 2 always admits the first two elements; otherwise x must differ from the value two slots back to respect the cap.

  4. 4
    Lines 6-7Commit the element

    Write x into nums[k] and advance k so the kept prefix grows.

  5. 5
    Lines 8Return the count

    k is the length of the valid prefix the grader checks.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Array shorter than or equal to 2 elements (all kept)
  • No duplicates at all
  • Every element identical (only two survive)
  • Exactly two of each value (nothing removed)
!

Common beginner mistakes

  • Comparing against nums[k-1] instead of nums[k-2], which wrongly allows only one copy
  • Comparing the candidate to the previous input element rather than the previous written element
  • Forgetting the k < 2 guard, causing a negative index on the first elements
Check your understanding

Why compare against nums[k-2] rather than the raw previous input value?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima