Two Pointers · LC #26
Remove Duplicates from Sorted Array
Classic fast/slow pointer pattern: slow pointer marks the next write position, fast pointer discovers new unique elements. Single pass, O(1) extra space.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a sorted array `nums` in-place, remove duplicates so each unique element appears only once. Return the count `k` of unique elements. Elements beyond `k` do not matter.
Sample I/O
Input: nums = [1,1,2] Output: k=2, nums = [1,2,_] Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: k=5, nums = [0,1,2,3,4,_,_,_,_,_]
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
The array is sorted, so duplicates are always adjacent. A slow pointer tracks where the next unique element should be written; a fast pointer scans ahead to find the next distinct value. When fast finds a new value, write it at slow's position and advance slow.
Core Concept
Slow pointer `k` starts at 1 (element 0 is always unique and already in place). Fast pointer `i` iterates from 1 to n-1. When `nums[i] != nums[i-1]`, a new unique value is found: write it to `nums[k]` and increment `k`. Return `k`.
When to use
In-place deduplication or compaction of a sorted array or stream. Also the template for "remove element" (LC 27), "remove duplicates II" (LC 80).
When NOT to use
Unsorted arrays - you need a hash set then. When you need the result in a new array (list comprehension / filter is cleaner).
Key Insights
What to Know Cold
- Because the array is sorted, `nums[i] != nums[i-1]` is sufficient to detect a new unique element.
- The write pointer `k` never overtakes the read pointer `i`, so reads are never overwritten before they are used.
- Initialising `k=1` implicitly keeps the first element in place.
- The same pattern handles "allow at most 2 duplicates" by comparing `nums[i]` with `nums[k-2]`.
- Return value is `k`, not `k-1` - it represents the count, not the last index.
1 example
Worked Examples
Fast/Slow Pointer Deduplication
[0,0,1,1,1,2,2,3,3,4] - compact unique elements to the front.
k=1. When nums[i] != nums[i-1], write nums[i] at nums[k] and increment k. After loop k=5, first 5 elements are [0,1,2,3,4].
def removeDuplicates(nums: list[int]) -> int:
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
nums[k] = nums[i]
k += 1
return kThe fast/slow pointer compaction template - reused in remove-element, Dutch-flag partition, and stream deduplication.