Run it
The two-pointer version with the array printed after each write, the same pattern applied to two sibling problems, and the off-by-one comparison that looks right and is not.
Two pointers, read and write
O(n) time, O(1) space.
The invariant is what makes it correct: everything before write is the deduplicated result so far. Naming that invariant out loud is worth more than the code, because it is what lets you verify the comparison is right.
The comparison is against nums[write - 1] — the last value kept — not against nums[read - 1], the previous value read. On sorted input those coincide, and using the kept value generalises correctly to the variants below.
Tracing it
[1, 1, 2, 2, 3]:
| read | nums[read] | nums[write−1] | Action | Array | write |
|---|
| 1 | 1 | 1 | Skip — duplicate | [1,1,2,2,3] | 1 |
| 2 | 2 | 1 | Write at 1 | [1,2,2,2,3] | 2 |
| 3 | 2 | 2 | Skip | [1,2,2,2,3] | 2 |
| 4 | 3 | 2 | Write at 2 | [1,2,3,2,3] | 3 |
Returns 3, and nums[:3] is [1, 2, 3]. The tail [2, 3] is leftover and explicitly allowed to be anything.
That leftover is worth pointing out, because the natural expectation is that the array is fully cleaned. The contract is only about the first write elements.
Why sorted matters
Duplicates in a sorted array are adjacent, so "have I seen this before?" collapses to "is it the same as the last one I kept?" — one comparison, no set, no memory.
On unsorted input this does not work and you need a set, which costs O(n) space, or a sort first, which costs O(n log n) time. Say which assumption you are relying on.
The read/write pattern
read visits every element exactly once. write lags behind, marking where the next kept element goes. Because write never overtakes read, the copy can never clobber something not yet examined — which is what makes in-place safe.
Compare against values[write - 1], the last element actually kept, not values[read - 1]. On a long run of duplicates those differ, and the second is wrong.
Why it returns a length
Nothing is reallocated, so the array keeps its original size and everything past write is leftover data. The caller uses values[:n]. This is the C-style convention the question comes from, and returning a new list instead would defeat the O(1) space requirement the question exists to test.
The same pattern solves "move zeroes to the end", "remove all instances of a value", and "allow at most two duplicates" — only the keep condition changes.
The variants
Allow up to k duplicates. The generalisation, and it is elegant — compare against the element k positions back:
With k = 1 this is the original; with k = 2 it allows each value twice. The write < k guard handles the start, and comparing against nums[write - k] asks "have I already kept k copies of this value?"
Remove all occurrences of a specific value:
Same shape, different condition. Recognising that these are one pattern with a varying predicate is the useful observation.
Move zeros to the end is the same again: write the non-zeros forward, then fill the remainder with zeros.
Unsorted input. Requires a set for O(n) time and O(n) space, or sorting first for O(1) space at O(n log n). State the trade rather than pretending in-place O(n) is available.
Edge cases
| Case | Result |
|---|
[] | 0 |
[1] | 1 |
All identical, [2,2,2] | 1 |
| All distinct | Unchanged length |
| Two elements equal | 1 |
| Not actually sorted | Wrong answer, silently |
The last row is the important one. The algorithm relies on duplicates being adjacent, and on unsorted input it removes only adjacent repeats and returns a length that is too large. It fails without any error, which is worse than raising.
If sortedness is not guaranteed, say so and ask — do not assume.
Why the write-pointer pattern generalises
This is one instance of a broader technique: a read pointer scanning and a write pointer compacting, used whenever an array must be filtered in place.
| Problem | Write condition |
|---|
| Remove duplicates (sorted) | Differs from the last kept |
| Remove a value | Not equal to the value |
| Move zeros to the end | Non-zero |
| Keep at most k duplicates | Differs from k positions back |
| Partition by a predicate | Predicate holds |
| Dutch national flag | Three regions, three pointers |
All of them are O(n) time and O(1) space, and all of them are the same loop with a different if. Recognising the family means you write it correctly the first time rather than re-deriving it.
The corresponding out-of-place version is a list comprehension — [x for x in nums if x != val] — which is clearer and uses O(n) space. Choose in-place only when the constraint requires it.
What it is testing
Do you use two pointers rather than deleting from the list? nums.remove(x) or del nums[i] inside a loop is O(n) per operation and shifts the elements you are iterating over — a double mistake.
Do you state the invariant? "Everything before write is the answer so far" is what makes the solution verifiable.
Do you compare against the last kept element, not the previous read one?
Do you notice that sortedness is required? And ask if it is not stated.
Do you know the tail is allowed to be garbage? The contract is the returned length, not the whole array.
Recap in one screen
- Sorted input means duplicates are adjacent, which allows one pass with O(1) space.
- A read pointer scans; a write pointer marks where the next kept element goes.
- Compare against the last kept element,
nums[write - 1], not the previous read one. - Elements past the returned length are undefined — that is part of the contract.
- The read/write compaction pattern covers remove-value, move-zeros and keep-at-most-k with a different condition.