Remove Duplicates from Sorted Array
Last Updated: March 31, 2026
Understanding the Problem
At first glance, removing duplicates from a sorted array seems trivial: just pick one of each value. But the in-place constraint makes it interesting. We can't create a new array and copy unique values over (well, we can, but that wastes space). We need to rearrange the original array so that unique elements sit at the front, and then tell the caller how many there are.
The fact that the array is already sorted is a huge advantage. All duplicates are grouped together, sitting right next to each other. So we never need to search the whole array to check if we've seen a value before. We just need to compare each element with the one before it (or the last unique one we placed). This observation is what makes the problem solvable in a single pass.
Key Constraints:
1 <= nums.length <= 3 * 10^4→ With n up to 30,000, O(n^2) means about 900 million operations, which is borderline. O(n) or O(n log n) is preferred.-100 <= nums[i] <= 100→ The value range is tiny (only 201 possible values). This means we could use a hash set or counting array, but since the array is sorted, we don't need to.nums is sorted in non-decreasing order→ This is the most important constraint. Duplicates are adjacent, so a single scan comparing neighbors is enough.
Approach 1: Using a Hash Set
Intuition
The most straightforward way to think about this: use a data structure that automatically ignores duplicates. A hash set does exactly that. We can collect all unique values, sort them (since the output needs to maintain order), and write them back into the array.
This approach ignores the sorted property entirely and uses extra space, so it's not ideal. But it's a clean mental starting point.
Algorithm
- Insert all elements from
numsinto a hash set to get unique values. - Convert the set to a list and sort it.
- Write the sorted unique values back into the first
kpositions ofnums. - Return
k, the number of unique elements.
Example Walkthrough
Input:
After collecting unique values into a set and sorting: {0, 1, 2, 3, 4}
Write them back into the first k positions of nums:
Code
- Time Complexity: O(n log n). Inserting n elements into a hash set is O(n). Converting to a list and sorting is O(k log k) where k is the number of unique elements (at most n). Overall: O(n log n).
- Space Complexity: O(n). The hash set and sorted list together use O(n) extra space in the worst case (when all elements are unique).
This approach works correctly but wastes space and ignores the sorted property entirely.
Since duplicates are already grouped together in a sorted array, can we just walk through the array once and place each new unique value in the right spot?
Approach 2: Two Pointers (Optimal)
Intuition
Since the array is sorted, duplicates are always adjacent. We don't need a hash set to detect them. We just need to compare each element with the last unique element we placed.
The insertPos pointer is always at or ahead of the last placed unique element. Everything before insertPos contains unique values in sorted order. The scanning pointer i always moves forward, and because the array is sorted, once we've placed a value at insertPos - 1, the only way to find a new unique value is to encounter something strictly greater.
This is essentially a stable filtering operation: we keep only the first occurrence of each value and discard the rest.
Algorithm
- If the array is empty, return 0.
- Initialize
insertPos = 1(the first element is always unique). - Iterate through the array starting from index 1.
- When
nums[i]is different fromnums[insertPos - 1], placenums[i]atnums[insertPos]and incrementinsertPos. - Return
insertPosas the count of unique elements.
Example Walkthrough
Code
- Time Complexity: O(n). A single pass through the array. Each element is visited exactly once, and each comparison and assignment is O(1).
- Space Complexity: O(1). Only one extra variable (
insertPos). No additional data structures.