Remove Duplicates from Sorted Array
EasyGiven an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once.
Return the number of unique elements k. The first k elements of nums should contain the unique elements.
Example
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements being 1 and 2.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements being 0, 1, 2, 3, and 4.
Explanation
Since the array is already sorted, all duplicates will be adjacent to each other. We can use the two pointers technique to solve this efficiently:
The Two Pointers Approach
Use two pointers to track positions:
- Slow pointer (k): Points to the position where the next unique element should be placed
- Fast pointer (i): Scans through the array looking for new unique elements
When we find a new unique element (nums[i] != nums[i-1]), we copy it to the slow pointer position and advance both pointers.
Step-by-Step Walkthrough
For input [0,0,1,1,1,2,2,3,3,4]:
Initial: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k=1 (first element is always unique)
i=1: nums[1]=0, nums[0]=0 → Same, skip
i=2: nums[2]=1, nums[1]=0 → Different! nums[1]=1, k=2
nums = [0, 1, 1, 1, 2, 2, 3, 3, 4]
i=3: nums[3]=1, nums[2]=1 → Same, skip
i=4: nums[4]=1, nums[3]=1 → Same, skip
i=5: nums[5]=2, nums[4]=1 → Different! nums[2]=2, k=3
nums = [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
i=6: nums[6]=2, nums[5]=2 → Same, skip
i=7: nums[7]=3, nums[6]=2 → Different! nums[3]=3, k=4
nums = [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
i=8: nums[8]=3, nums[7]=3 → Same, skip
i=9: nums[9]=4, nums[8]=3 → Different! nums[4]=4, k=5
nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
Return k=5, unique elements at indices 0-4
Idea Map
For each element from index 1 to end:
Is nums[i] different from nums[i-1]?
Yes: Copy to nums[k], k++
No: Skip (duplicate)
Complexity Analysis
Time Complexity
O(n) - Single pass through the array with the fast pointer.
Space Complexity
O(1) - In-place modification using only two pointer variables.
Code
def removeDuplicates(nums):
Main function that takes sorted array and removes duplicates in-place.
if not nums:
Edge case: empty array has 0 unique elements.
return 0
Return 0 for empty array.
k = 1 # Slow pointer - position for next unique element
First element is always unique, so k starts at 1.
for i in range(1, len(nums)): # Fast pointer
Fast pointer scans from index 1 to end of array.
if nums[i] != nums[i - 1]: # Found new unique element?
Compare current element with previous. Different means new unique!
nums[k] = nums[i] # Copy to slow pointer position
Copy unique element to the k-th position.
k += 1 # Advance slow pointer
Increment k to point to next position for unique element.
return k # Number of unique elements
Return k - the count of unique elements in the modified array.
public int removeDuplicates(int[] nums) {
Main method that takes sorted array and returns count of unique elements.
if (nums.length == 0) {
Edge case: empty array check.
return 0;
Return 0 for empty array.
}
End of empty check.
int k = 1; // Slow pointer
First element is always unique, k starts at 1.
for (int i = 1; i < nums.length; i++) { // Fast pointer
Fast pointer scans from index 1 to end.
if (nums[i] != nums[i - 1]) { // New unique element?
Compare with previous element to find unique.
nums[k] = nums[i]; // Copy to slow pointer position
Copy unique element to position k.
k++;
Advance slow pointer.
}
End of unique check.
}
End of for loop.
return k;
Return count of unique elements.
}
End of method.
int removeDuplicates(vector<int>& nums) {
Function takes vector by reference for in-place modification.
if (nums.empty()) {
Edge case: check for empty vector.
return 0;
Return 0 for empty vector.
}
End of empty check.
int k = 1; // Slow pointer
First element is unique, k starts at 1.
for (int i = 1; i < nums.size(); i++) { // Fast pointer
Fast pointer scans from index 1.
if (nums[i] != nums[i - 1]) { // New unique?
Compare current with previous element.
nums[k] = nums[i];
Copy unique element to position k.
k++;
Advance slow pointer.
}
End of if statement.
}
End of for loop.
return k;
Return count of unique elements.
}
End of function.
Edge Cases & Common Mistakes
Empty array handling
Always check if the array is empty before processing. Return 0 immediately.
Single element array
A single element has no duplicates, so return 1. The loop won't execute.
Why compare with i-1?
Since array is sorted, duplicates are adjacent. Comparing nums[i] with nums[i-1] catches all duplicates efficiently.
Don't actually delete elements
The problem only requires placing unique elements at the front. Elements after index k don't matter.
Related Problems
Understanding Two Pointers
The two pointers technique is fundamental for array manipulation problems. It allows in-place modifications with O(1) space complexity while maintaining O(n) time complexity.
Learn more about Two Pointers →Disclaimer: This problem is for educational purposes. Practice the 'Remove Duplicates from Sorted Array' problem on LeetCode.