Algorithms · interview field notes

Remove Duplicates II: keep at most two of each

A sorted array, trimmed in place so no value appears more than twice — return k, the new length, with the answer packed into the first k slots and O(1) extra memory. Press Play on each figure and leave able to explain the one-pointer trick — not just type it.

given (sorted)return kfirst k slots hold the answer

[1,1,1,2,2,3]5[1,1,2,2,3,_]

[0,0,1,1,1,1,2,3,3]7[0,0,1,1,2,3,3,_,_]

Every value now appears at most twice. The _ marks slots past k — leftover junk the grader ignores, so you never clean them up.

How do you cap every value at two copies in a single pass, with no second array?

Why compare the incoming value to the slot two behind the writer — and not two behind the reader?

Start here

Meet the three things you track

Before any code, just three characters. The whole algorithm is these three working together — once they click, the one-liner everyone memorizes reads itself. Step through and meet each one.

The three things you keep track of

nums — the array, which we rewrite in place

nums

The sorted array itself. We don't make a copy — we overwrite its front as we go.

The read pointer. The position we're examining right now; its value is nums[r]. It walks left → right, visiting every spot once.

The write pointer. The next slot to fill at the front — and, because it only moves when we keep a number, also the count of keepers so far.

Everything happens on one array, nums. It comes in sorted, and we'll move the survivors to the front of this very same array — no second list, no extra memory.

01 / 04

The plot, in one breath

r reads every slot left to right. k writes the keepers to the front of nums. Both start at 0; the only decision — keep or skip — is what the next three sections unpack.

Why one pass is even possible

Sorted ⇒ duplicates are adjacent

Because the input is sorted, every copy of a value sits in one contiguous run. So the task isn't really "find duplicates anywhere" — it's "trim each run down to two." Watch the runs, then the survivors.

Sorted means duplicates are adjacent

2× → keep 2

4× → keep 2, drop 2

1× → keep 1

2× → keep 2

kept so far = 0

The array is sorted, so equal values are never scattered — every copy of a number sits in one unbroken run. That single fact is what makes one pass possible.

01 / 06

The catch: we don't want to find the runs first and copy survivors into a new array — that's O(n) extra space. We need to trim in place, deciding each element with a glance at what we've already kept.

The crux

Compare to the slot two back

Here is the single idea the whole problem turns on — and it's simpler than it sounds. You're allowed two of each value, so before you keep a new number, you just glance two spots back at what you've already kept. Step through it:

The one test · is this a third copy?

numbers we've kept so far

next slot

The goal: keep at most two of any number. As we copy the keepers to the front, every newcomer faces one question — would it be a third copy? Here's the shortcut that answers it instantly.

01 / 05

In one sentence

If the number two spots back is the same as the newcomer, you've already got two of them — so the newcomer would be a third. Keep it only when they differ. That single check is the entire algorithm.

Watch it run

The full pass, step by step

Now the engine in motion on [0,0,1,1,1,1,2,3,3]. Follow the two pointers: r never stops, k only advances on a keep — and where they split is exactly the duplicates being discarded.

Full run · step debugger · [0,0,1,1,1,1,2,3,3]

rread▼

kwrite▼

executioninitialise

▸1k = 0

▸2for r in 0 … n−1:

3 if k < 2 or nums[r] ≠ nums[k−2]:

4 nums[k] = nums[r]

5 k += 1

6return k

watch · variables right now

read pointer — scans every index, left → right

write pointer & count — next slot to fill

Both initialised to 0. Each loop turn plays as two steps: first read & test (r moves), then write & advance (k moves).

kept · nums[0..k)

just written

skipped (3rd copy)

nums[k−2] · compared

Both pointers start at index 0. To make the mechanism visible, every loop turn is shown as two steps: first read & test — r advances and we evaluate the if — then, only if we keep, write & advance — we copy the value and bump k. So you'll see r and k move on different steps.

01 / 18

Say this

"r reads every slot; k writes only the keepers. When I keep the 2 at r = 6, I overwrite a leftover 1 — that's fine, k never overtakes r, so I never clobber data I still need to read. The gap between r and k is the count of dropped duplicates."

The same trick, any limit

It's all one dial

"At most two" was never special. Change the cap to m and the comparison index follows it to k − m. Flip the dial and watch the same code solve every version.

One knob · keep at most m of eachfig

if k < 2 or nums[r] != nums[k−2]: keep

survivors = [1, 1, 2, 2, 3] · k = 5

The body never changes — only the constant m. Swap the cap and the comparison index k−m move together, and the same five lines solve “remove duplicates” (m=1), “at most twice” (m=2), or any limit. That’s the whole pattern in one dial.

The transferable habit

The pattern, and its siblings

One reflex carries across a whole cluster: when you must rewrite an array in place, keep a slow write pointer and a fast read pointer, and let a tiny condition decide what gets written. These all rhyme.

“Remove every copy of a value.”write ptr

Walk with r, write nums[r] whenever it isn't the target value. k ends as the new length.

“Remove duplicates — keep one.”k − 1

This problem's cousin. Keep nums[r] only when it differs from the last kept, nums[k − 1].

“Move all zeroes to the end.”write ptr

Write the non-zeros forward with k, then fill [k, n) with zeros. Order preserved.

“Merge two sorted arrays in place.”back ptrs

Same two-pointer skeleton, but written from the back so writes never trample unread input.

“Sort 0s, 1s, 2s in one pass.”3 ptrs

Dutch-flag partition — three write pointers carving the array into regions live.

“Dedupe a sorted linked list.”slow/fast

The identical idea on nodes: a slow tail you extend, a fast cursor that scans ahead.

What trips people up

The edge cases that break naive code

Four traps an interviewer will probe — each one handled by keeping the comparison anchored to k.

comparing to nums[r − 2]

The classic bug. Once a skip happens, the reader and writer diverge, and nums[r − 2] points into stale, not-yet-overwritten input. Always compare to nums[k − 2] — the kept region.

arrays shorter than 3

With 0, 1, or 2 elements nothing is ever a third copy. The k < 2 guard keeps them all and returns the length unchanged — no special-casing needed.

all elements identical

[2,2,2,2,2] → keep the first two, skip the rest, return 2. A good sanity check that the cap actually fires.

negatives and the tail

Values can be negative — you compare equality, never sign, so it's irrelevant. And don't waste effort cleaning slots past k: the judge ignores them entirely.

Print this on the back of your hand

The interview cheat-sheet

“What's the approach?”

Two index pointers, both starting at 0: r reads every slot, k writes the keepers. For each r, if k < 2 or nums[r] != nums[k − 2], write nums[k] = nums[r] and bump k. Return k. O(n) time, O(1) space.

“Why two slots back?”

The kept prefix is sorted. If nums[r] == nums[k − 2], then nums[k − 2] and nums[k − 1] are already two copies of it — writing it would make a third.

“Why k, not r?”

You must compare against what you've kept, not the raw input. After any skip, r − 2 drifts into stale data; k − 2 stays anchored to the answer.

“Generalize it.”

For "at most m," compare against nums[k − m]. m = 1 is plain remove-duplicates. Same five lines.

the whole solution · pythonO(n) time · O(1) space

def removeDuplicates(nums):

    k = 0                                  # write pointer + count of keepers

    for r in range(len(nums)):             # r reads every index, left -> right

        if k < 2 or nums[r] != nums[k-2]:  # keep unless it'd be a 3rd copy

            nums[k] = nums[r]

            k += 1

    return k

One loop, one comparison. nums[k − 2] reads from the kept region — never nums[r − 2] from the original — which is the whole reason overwriting in place stays correct.

The one-liner to land

"Read pointer r, write pointer k, both from 0. Keep nums[r] only when k < 2 or it differs from nums[k − 2] — the slot two behind the writer — because a sorted, deduped prefix means that match would be a third copy. One pass, in place."