vizlearn

Remove duplicates from a sorted array in place

Interview QuestionsBy Updated

Two pointers moving the same way. Read scans every element; write marks the end of the kept prefix. When read finds something new, copy it back to write and advance. O(n) time, O(1) extra space — and the function returns a length, because nothing was reallocated.

Overview

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.

Lists & arraysCoding problemEasy

Step through it

What to watch

  • write only advances on a genuinely new value.
  • The comparison is against the last kept element, not the previous one read.
  • The tail is left as stale data — that is why a length is returned.

Say this out loud

"Fast and slow pointers. Read scans, write marks the end of the deduped prefix, and I copy back only when the value differs from the last kept one. O(n) time, O(1) space, and I return the length because the tail is stale."

Remove duplicates from a sorted array in place

Remove duplicates from a sorted array in place and return the new length.

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.

Run it in Python

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.

dedupe.pyPython 3
Output
How the code works
  1. values[read] != values[write - 1]Compare with the last element actually kept. Using values[read - 1] instead happens to agree on sorted input and is the wrong invariant to carry into the variants.
  2. write += 1 only on a keepwrite is the length of the answer so far, which is why returning it at the end needs no separate counter.
  3. write never overtakes readThe safety argument for writing into the array you are reading. Every slot written has already been consumed.
  4. if write < 2 or v != values[write - 2]:The at-most-two variant. Same skeleton, one different condition — which is what makes this pattern worth recognising rather than memorising.
Change one thing
  • Print the whole array rather than values[:n]. The stale tail is exactly why the function cannot just return the array.
  • Adapt it to remove every instance of a given value. One condition changes and nothing else does.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does the function return a length rather than a list?
  2. The current element is compared against:
  3. Writing into the array while reading it is safe because:





 Cheat sheet
Remove duplicates from a sorted array in place
Two pointers moving the same way. Read scans every element; write marks the end of the kept prefix. When read finds something new, copy it back to write and advance. O(n) time, O(1) extra space — and the function returns a length, because nothing was reallocated.
INTERVIEW · vizlearn.in/interview/remove-duplicates-in-place.html
More in Interview
InterviewRotate an array by kInterviewProduct of array except selfInterviewHow does a Python dict work?InterviewWhy must dictionary keys be hashable?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact