Removing Duplicates from Sorted Arrays
You'll learn how to efficiently eliminate duplicate values from a sorted array while keeping the unique elements in their original order.
The Core Idea
When you have a sorted array with duplicates, you don't need to create a new array or use complex searching. Since identical values are already grouped together, you can use a two-pointer technique to modify the array in-place—keeping only one copy of each unique value and compacting them toward the front.
How It Works
Imagine a row of labeled boxes on a shelf, sorted alphabetically, with some duplicate labels. You have two hands:
- Read pointer: scans through every box, left to right
- Write pointer: marks where the next unique box should go
Start both at the beginning. Move the read pointer forward. Whenever it finds a box with a different label than the previous one, copy that box to the write pointer's position and advance the write pointer. Skip duplicates without copying them.
When finished, the first few positions contain all unique values in order, and the write pointer tells you how many unique items you have.
Why the Two-Pointer Technique?
Since the array is sorted, duplicates sit next to each other. You only need to compare each element with the previous one—not search the whole array. One pointer tracks where you're reading from, the other tracks where you're writing unique values. This runs in a single pass with no extra array needed.
Key Takeaway: The two-pointer technique removes duplicates from sorted arrays in-place by maintaining one pointer to scan elements and another to track where unique values should be written, leveraging the sorted order for efficiency.