Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Remove duplicates in place from a sorted array and return the count k of unique values. The naive answer copies uniques into a new array; the canonical answer uses a slow write pointer and a fast read pointer — whenever nums[fast] differs from the last kept value, advance slow and copy. Return slow + 1.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you exploit the sorted property (duplicates are adjacent) to dedup in O(1) space with two pointers, instead of reaching for a set or a second array.
Where candidates slip
Returning the array instead of the count k, or using a single index for both reading and writing so you overwrite values before comparing them.
How to stand out
Note that 'sorted' means equal values are adjacent — that's the property that lets one comparison (nums[fast] vs nums[slow]) decide everything. Mention the slow pointer is a length-minus-one index, so return slow + 1.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewRemove duplicates, return unique countIs the array sorted?NoYesExplore the full treeCollapse the tree
nums = [0,0,1,1,2]How to read it:slow points at the last unique kept; fast scans ahead. On a new value, slow advances and copies it.
- Frame 1
slow=0, fast=1nums[1]=0 == nums[0]=0 → duplicate, skip
s↓0[0]f↓0[1]1[2]1[3]2[4] - Frame 2
slow=0, fast=2nums[2]=1 != nums[0]=0 → new → slow=1, nums[1]=1
0[0]s↓1[1]f↓1[2]1[3]2[4] - Frame 3
slow=1, fast=3nums[3]=1 == nums[1]=1 → duplicate, skip
0[0]s↓1[1]1[2]f↓1[3]2[4] - Frame 4
slow=1, fast=4nums[4]=2 != nums[1]=1 → new → slow=2, nums[2]=2
0[0]1[1]s↓2[2]1[3]f↓2[4] - Frame 5
donereturn slow + 1 = 3; first 3 slots are [0,1,2]
0[0]1[1]s↓2[2]1[3]2[4]
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Copy Uniques to a New Array (Naive)
1Hint 1Explore hintHide hint
Forget in-place for a second: how would you list the distinct values of a sorted array into a fresh list?
2Hint 2Explore hintHide hint
Append nums[i] whenever it differs from the previous element (or it's the first element).
3Hint 3Explore hintHide hint
That list IS the uniques in order. To satisfy the in-place spec you'd then copy it back into nums and return its length — which is exactly the extra space we want to avoid.
A · Core idea
Scan left to right and collect each value that differs from its predecessor into a separate list. Because the array is sorted, that list is precisely the set of unique values in their original order. To honour the in-place contract you'd copy the list back into nums and return its size.
Why this is the natural first attempt. "Remove duplicates" reads like "build the list of things that aren't duplicates". Allocating a fresh container and appending the survivors is the most direct mental model — no pointer juggling, no overwrite hazards, just a filter. It's correct and easy to reason about.
Why the comparison is to the previous element. In a sorted array, a value is a duplicate exactly when it equals the one just before it. So nums[i] is new iff i == 0 || nums[i] != nums[i-1]. That single test is all the dedup logic you need — the sortedness does the rest.
Why it falls short of the spec. The problem explicitly demands an in-place transformation with the answer living in nums[0..k-1]. A separate list uses O(n) auxiliary memory, which defeats the purpose — and the copy-back is busywork. Interviewers pose this exact problem to see whether you can avoid the extra array.
Why we still mention it. It anchors correctness: it's obvious the filtered list is right. From there, the leap is realising the destination buffer can be nums itself, written by a second pointer that always trails the reader — which is the optimal solution.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1,1,2]i=0
first element → append 1
result = [1]k = 2, result = [1, 2]C · Code with teaching comments
Reference implementation previewpublic int removeDuplicates(int[] nums) { List<Integer> unique = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (i == 0 || nums[i] != nums[i - 1]) { unique.add(nums[i]);Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The filter rule 'keep nums[i] when it differs from nums[i-1]' is the entire algorithm in one line. The only thing wrong with the naive version is where it writes — a new array. Redirect those writes into the front of nums and the extra space vanishes.
ComplexityO(n) time, O(n) space — One linear scan to build the list (O(n) time), plus a result list that can hold up to n elements (O(n) space). Copying back is another O(n) pass but doesn't change the asymptotics.
E · Edge cases and pitfalls5nums = [5] — i=0 appends 5; result = [5], k = 1.Explore edge casesHide edge cases
Edge cases handled
nums = [5]i=0 appends 5; result = [5], k = 1.nums = [2,2,2]Only the first 2 is appended; k = 1.
Pitfalls
- Allocating a list defeats the O(1)-space goal — fine as a baseline, not as the final answer.
- Forgetting to copy the list back into nums — the judge inspects nums itself.
- Returning the list instead of its length.
Approach 2 of 2 · Optimal
Slow/Fast Two Pointers (Optimal)
1Hint 1Explore hintHide hint
You don't need a second array — you can reuse the front of nums as the output region. What invariant would let you safely overwrite slots you've already passed?
2Hint 2Explore hintHide hint
Keep slow = index of the last unique value written, and fast scanning ahead. Everything in nums[0..slow] is the deduped prefix so far.
3Hint 3Explore hintHide hint
When nums[fast] differs from nums[slow], it's a new unique: increment slow and copy nums[fast] there. fast always leads slow, so you never overwrite an unread value. Return slow + 1.
A · Core idea
Maintain two indices. slow is the position of the last unique value we've committed to the front of the array; fast races ahead looking for the next value that breaks the current run. The region nums[0..slow] is always the correctly deduplicated prefix.
The invariant that makes it safe. At every moment, nums[0..slow] contains the unique values seen so far, in order, and fast > slow always. Because the write pointer slow never catches up to the read pointer fast, any slot we overwrite (nums[slow+1]) is one fast has already moved past — its original content is no longer needed. This is the same write-head-trails-read-head guarantee that makes in-place array compaction possible without a buffer.
Why one comparison is enough. The array is sorted, so all copies of a value form a contiguous block. The first element of each block is the one we keep; the rest equal it. So nums[fast] is a new value precisely when nums[fast] != nums[slow] — we compare against the last kept value, not a whole set. When they're equal, fast is still inside the current run and we simply skip; when they differ, fast has entered a new run, so we advance slow and copy. Sortedness collapses 'have I seen this before?' from a set membership query into a single adjacent comparison.
Why we write at `slow + 1`, not `slow`. slow already holds a committed unique value we must not clobber. The next unique belongs in the slot immediately after it. So on a new value we first do slow++ to open the next slot, then nums[slow] = nums[fast]. Doing it in the other order would overwrite the value we just kept.
Why the answer is `slow + 1`. slow is the index of the last unique, and indices are zero-based, so the count of uniques is slow + 1. The leftover tail past index slow still holds stale values, but the problem says those slots are don't-care, so we leave them. Guard the empty array (n == 0 → 0) since slow starting at 0 assumes at least one element exists.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [0,0,1,1,2]Array state
skip dup
fast=1: 0 == 0 → no write
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Two pointers at different speeds turn a 'filter into a new array' problem into an in-place overwrite. The crucial realisation is that the survivors are always fewer than the elements scanned, so a trailing write pointer can never overtake the reader — the front of the array doubles as your output buffer for free.
ComplexityO(n) time, O(1) space — fast makes one pass over the array (O(n)); each step does O(1) work. slow only ever advances, and we use a constant number of variables → O(1) extra space.
E · Edge cases and pitfalls7nums = [5] — The fast loop never runs; return slow + 1 = 1.Explore edge casesHide edge cases
Edge cases handled
nums = [5]The fast loop never runs; return slow + 1 = 1.nums = [1,1,1,1]Every comparison is equal, slow stays 0, return 1.nums = [1,2,3]Every value is new, slow ends at 2, return 3; array is unchanged.
Pitfalls
- Writing nums[slow] = nums[fast] before incrementing slow — overwrites the last kept unique.
- Comparing nums[fast] to nums[fast-1] works too, but comparing to nums[slow] is the canonical, copy-safe form.
- Returning slow instead of slow + 1 — off by one.
- Forgetting the empty-array guard when starting slow at 0.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int removeDuplicates(int[] nums) { if (nums.length == 0) { return 0; } int slow = 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Off-by-one on the return value
slow is the zero-based INDEX of the last unique, not the count. The number of uniques is slow + 1; returning slow undercounts by one.
Explore the code comparisonHide the code comparison
Off-by-one on the return value
slow is the zero-based INDEX of the last unique, not the count. The number of uniques is slow + 1; returning slow undercounts by one.
Don't write this
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow; // index, not countWrite this instead
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;2Writing before advancing the write head
Doing nums[slow] = nums[fast] and then slow++ overwrites the unique value currently at slow, corrupting the prefix.
Explore the code comparisonHide the code comparison
Writing before advancing the write head
Doing nums[slow] = nums[fast] and then slow++ overwrites the unique value currently at slow, corrupting the prefix.
Don't write this
if nums[fast] != nums[slow]:
nums[slow] = nums[fast] # clobbers the last kept unique
slow += 1Write this instead
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]3Reaching for a hash set on a sorted array
A set ignores the sorted structure and spends O(n) extra space. The whole point is that sortedness makes one adjacent comparison enough for O(1) space.
Explore the code comparisonHide the code comparison
Reaching for a hash set on a sorted array
A set ignores the sorted structure and spends O(n) extra space. The whole point is that sortedness makes one adjacent comparison enough for O(1) space.
Don't write this
seen = set()
k = 0
for x in nums:
if x not in seen:
seen.add(x)
nums[k] = x
k += 1
return kWrite this instead
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1Revise
Carry the pattern into the interview
Pattern to remember
Slow/fast write-pointer compaction
Code pattern to memorize
if n == 0: return 0
slow = 0
for fast in 1..n-1:
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1Rules to remember
- 1
slowmarks the last unique kept;fastscans ahead for the next new value. - 2Compare
nums[fast]tonums[slow]— the array is sorted, so duplicates are adjacent. - 3Only write when you find a new value, so you never overwrite an element you still need.
- 4Return the count
slow + 1, not the array — the firstkslots hold the answer. - 5Handle the empty array up front:
n == 0must return0. - 6
slowis a length-minus-one index, so the unique count is alwaysslow + 1.
Use this pattern when
- Sorted array where equal elements are guaranteed adjacent
- In-place compaction with `O(1)` extra space
- You need the count of distinct elements, leftover tail can be ignored
- The 'keep some, drop the rest' family — dedup, remove-element, move-zeroes
Choose another pattern when
- Array is unsorted → duplicates aren't adjacent; sort first or use a hash set
- You must preserve every duplicate's position → this destroys them
- Need the removed elements too → don't overwrite, collect instead
- Order doesn't matter and you can allocate → a set is simpler
Interview takeaway
Two pointers moving at different speeds — a slow write head and a fast read head — is the canonical way to compact an array in place. Because the input is sorted, equal values cluster, so a single adjacent comparison decides keep-or-skip. The same slow/fast shape solves Remove Element, Move Zeroes, and Remove Duplicates II.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical slow/fast two-pointer compaction. Recognise it whenever you must keep some elements and drop others in place, in order, with O(1) space. The sorted input lets a single adjacent comparison decide each element. Same shape as Remove Element, Move Zeroes, and Remove Duplicates II.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Remove Duplicates from Sorted Array IIAllow each value at most twice — compare nums[fast] to nums[slow-1] instead of nums[slow].
- Remove ElementSame slow/fast compaction, but the keep condition is nums[fast] != val.
- Move ZeroesKeep non-zeros with a write pointer, then fill the tail with zeros.
- Remove Duplicates from Sorted ListComing soonSame idea on a linked list — skip nodes equal to the current head.