Remove Duplicates from Sorted Array
How to compact a sorted array down to one copy of every value, in place, in a single pass.
The job
You have a SORTED array that may contain duplicate values. Remove the duplicates in place so each value appears once, and report how many unique values remain.
The obvious way
Build a set of the values seen so far, or a brand new array, and copy in only the values not already recorded.Works, but needs a second data structure the size of the input — not truly in place.
The idea
Because the array is sorted, every duplicate of a value sits immediately next to it. So the only thing worth remembering is the LAST value kept — compare the next candidate to just that one number, and swap it forward the moment it differs.
Think of it like this. Walking down an alphabetically sorted bookshelf, keeping one copy of each title. You never need to remember the whole shelf you have already passed — only the very last book you decided to keep, since any earlier duplicate would already be sitting right next to it.
Keeping only the first copy of each value
10 sorted numbers, some repeated. Keep exactly one copy of each value, in place, and report how many that is.
def remove_duplicates(nums):
write = 0
for read in range(1, len(nums)):
if nums[read] != nums[write]:
write += 1
nums[write], nums[read] = nums[read], nums[write]
return write + 1This run
5 unique values out of 10 — compacted to the front of the array in one pass, no extra storage.
The names you just watched
write and read
`write` marks the last confirmed-unique value. `read` scans everything after it, comparing each candidate to that one remembered value — never to the whole kept prefix.
Sorted is what makes this cheap
Because duplicates are guaranteed adjacent, one comparison per element is enough. On an unsorted array the same trick would need a hash set instead.
A swap keeps every bar visible
Swapping `write` and `read` — instead of directly overwriting — means every original value stays on screen exactly once; it just ends up on the "duplicates" side of the boundary.
How to spot this shape
The tell: The input is sorted, duplicates (or a similar local pattern) are guaranteed to sit next to each other, and you can decide "keep or skip" by comparing only to what you kept most recently.
Reach for it when
- The array is explicitly sorted.
- The task is phrased as "remove duplicates" or "compact in place."
- A brute-force answer uses a hash set or a second array to track what has been seen.
- Every decision only needs to look at ONE remembered value, not the full history.
Not this when
- The array is not sorted — duplicates could be anywhere, and this needs a hash set instead.
- You need to allow each value up to K times, not exactly one — the comparison target has to look further back.
- The relative order of survivors does not matter — sorting or counting may be simpler.
Practice
6 problemsThe lesson, exactly. write only advances when read finds a value different from the last kept one.
Compare against the value two slots behind write instead of one — that is what lets each value appear up to twice.
The same write/read walk with a different keep-condition — "is it non-zero" instead of "is it new."
Drop the "sorted" requirement and the keep-condition becomes "is it not equal to a given value" — no adjacency needed at all.
A write pointer moving FASTER than read this time — every zero needs to write twice — worked from the back to avoid overwriting unread values.
Sort first, then a two-pointer sweep that skips duplicate values exactly the way this lesson skips them — but to count pairs, not to compact the array.