You're given an integer array nums that is already sorted in non-decreasing order. Some values repeat, and repeats always sit next to each other. Your job is to remove the duplicates in place so that every unique value appears exactly once, while keeping their original relative order.
Let k be the number of unique values. After you're done:
k.k slots of nums must hold those unique values in sorted order.k - 1 doesn't matter — the judge ignores it.You must do this in place with O(1) extra space in the optimal solution — no allocating a second array whose size grows with the input.
write index marking the next unique slot and a fast read index scanning ahead. Advance write only when you hit a value different from the one already there.nums is sorted, every occurrence of a value is contiguous. Once you move past a value it can never reappear later, so the only element you can collide with is the most recent unique one.k elements are validated. Anything after them is leftover and completely ignored.nums[i] against nums[k - 2] instead of nums[k - 1], so a value is allowed to survive twice — the "keep at most two duplicates" variant.Input: nums = [1,1,2] Output: 2 The unique values are 1 and 2, so k = 2 and the first two slots become [1, 2, _]. The trailing slot is ignored.
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5 The unique values are 0, 1, 2, 3, 4, so k = 5 and the first five slots become [0, 1, 2, 3, 4, _, _, _, _, _].
- 1 <= nums.length <= 3 * 10^4 - -100 <= nums[i] <= 100 - nums is sorted in non-decreasing order.
This is the canonical introduction to the slow-write / fast-read two-pointer pattern — the same engine behind Move Zeroes, Remove Element, and quicksort's partition step. The whole solution rests on one property of the input: because it's sorted, every copy of a value sits next to its twin.
write index (where the next kept value goes) and a read index (scanning ahead). Different speeds, one pass.write never runs ahead of read.Given a sorted array nums, remove duplicates in place so each unique value appears once, keeping order. Return k, the count of unique values; the first k slots must hold them. Anything past index k-1 is ignored.
Worked example — nums = [0, 0, 1, 1, 1, 2]
read → 0 0 1 1 1 2 write: ▲ keep 0 (write=1) · skip 0 · keep 1 (write=2) · skip 1,1 · keep 2 (write=3) first k=3 slots: [0, 1, 2] → return 3
“Is the array guaranteed sorted?”
Yes — that's what makes duplicates adjacent. Without it, you'd need a hash set or a sort first.
“Can the array be empty?”
Not here (length >= 1). If it could, k would be 0.
“What if every element is identical?”
Then k = 1 — only the first slot is meaningful.
“What if there are no duplicates at all?”
k = n and the array is left unchanged.
“What exactly do I return, and what happens to the tail?”
Return k; only the first k slots are checked. Values beyond them are leftover and ignored.
“Does it need to be O(1) extra space?”
Yes for the optimal — no second array whose size grows with the input. The two-pointer overwrite achieves that.
A couple of quick questions.
The array is sorted, so all duplicates are adjacent — correct?
I return the count of uniques, and only the first k slots need to be right?
Should the optimal be in place with O(1) extra space?
Then I'll use two pointers: a slow write index and a fast read index.
In a sorted array, every occurrence of a value is contiguous. Once you move past a value, it can never reappear later — so the only element the current one can duplicate is the most recent unique you kept. That collapses "have I seen this before?" from a full search into a single comparison.
Keep a slow write index marking the next unique slot and a fast read index scanning every element. Whenever read finds a value different from nums[write-1], copy it to write and advance write. One pass, no extra array.
Because write only advances on a new unique and read advances every step, write <= read always holds. So every cell you overwrite is one you have already read — you never clobber data you still need.
| Copy uniques to a side list | Two pointers | |
|---|---|---|
| Idea | Collect uniques elsewhere, write back | Overwrite in place with a write index |
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
The full code for both is in the Approaches selector below.
Key takeaway
When a sorted array must be de-duplicated in place, use slow-write / fast-read two pointers: read scans every element, write marks the next unique slot, and you copy only when the value differs from the last kept one. O(n) time, O(1) space — and the overwrite is always safe because write trails read.