Remove Duplicates from Sorted Array is a classic warm-up for the two-pointer pattern. Because the array is already sorted, every duplicate sits right next to its twin — and that one fact lets us clean the array in a single pass using O(1) extra space.
Problem. Given a sorted integer array nums, remove the duplicates in place so each unique
value appears once. Return k, the number of unique values. The first k slots of nums must hold
those unique values in order; what is left past slot k does not matter.
Example: nums = [1, 1, 2, 2, 3, 4, 4] → unique prefix [1, 2, 3, 4], so return 4.
The slow way first
The obvious idea: copy nums into a set to drop duplicates, sort the set, and write it back. That works, but it uses O(n) extra space for the set — and the problem specifically asks us to do it in place.
The question to ask: the array is sorted — what does that buy me? It means equal values are always adjacent. So I never need a set to detect a duplicate; I only need to compare each value to the last unique one I kept.
The idea: a write pointer and a read pointer
Keep two indices. slow points at the last unique value we have committed to the front of the array. fast scans forward looking at every value. When nums[fast] differs from nums[slow], we have found a brand-new value: bump slow forward one slot and copy the new value into it. When they are equal, it is a duplicate, so we just let fast move on.
The key insight: slow always points at the end of a clean, deduped prefix. Every write lands just past it, so the unique values stay packed at the front and in order.
Walk through it
Step through the animation. slow (above) holds the unique prefix; fast (below) scans ahead. The two 1s match, so the second 1 is skipped. When fast hits the first 2, it differs from nums[slow], so slow advances and 2 is copied in. The same happens for 3 and 4. The faded cells at the end are leftovers we no longer count.
Pseudocode
if the array is empty: return 0
slow = 0 # end of the unique prefix
for fast from 1 to last index:
if nums[fast] != nums[slow]: # found a new value
slow += 1
nums[slow] = nums[fast] # write it just past the prefix
return slow + 1 # count of unique valuesThe Python solution
def remove_duplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1slowis the write pointer — it marks the last slot of the clean, deduped prefix.fastis the read pointer — it visits every value once via theforloop.- Line 6 is the whole trick: because the array is sorted,
nums[fast] != nums[slow]is true exactly whenfastreaches a value we have not kept yet. - When that happens, we advance
slowand copy the new value in (lines 7 and 8), extending the prefix by one. - The answer is
slow + 1—slowis the last index of the prefix, so its length is one more.
Complexity
| Case | Time | Notes |
|---|---|---|
| Set + rewrite | O(n log n) (moderate) | extra set, then sort back |
| Two pointers (this solution) | O(n) (moderate) | one pass, in place |
O(1) (fast)We touch each element once and write nothing to a side structure, so the extra space is O(1). That in-place, constant-space property is exactly what the problem is testing.
When this pattern shows up
A slow write pointer + fast read pointer is the go-to move whenever you must compact or filter an array in place: remove duplicates, move zeros to the end, remove a target value, or keep at most k of each. The slow pointer marks where the next kept element goes; the fast pointer finds the elements to keep.
This trick relies on the array being sorted so duplicates are adjacent. On an unsorted array, two
equal values can be far apart, and comparing only to nums[slow] would miss them — you would need a set
or a sort first.
Practice
For nums = [1, 1, 2, 2, 3, 4, 4], when fast reaches the first 2, what does slow become and what gets written?
1. Why does comparing nums[fast] to nums[slow] correctly find every duplicate?
2. What does slow point at during the scan?
3. Why does the function return slow + 1 instead of slow?
4. What is the extra space this solution uses?