Part 2 · Problems · Two pointers
Remove Duplicates from Sorted Array
#26 · Easy · LeetCode
Sorted array. Remove duplicates in place so each value appears once. Return the new length k. The first k slots hold the answer.
[0,0,1,1,1,2,2,3,3,4] -> 5, first five = [0,1,2,3,4]
Ask before coding
- Sorted ascending?
- What's after k doesn't matter?
Hint
Sorted means duplicates are neighbours.
Approach
Writer w starts at 1. For each value, if it differs from the last written value nums[w-1], write it at w.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let w = 1;
for (let r = 1; r < nums.length; r++) {
if (nums[r] !== nums[w - 1]) nums[w++] = nums[r];
}
return w;
}Traps
- Compare with the last written value, not with nums[r-1]. Both work here, but the first generalises.
Say out loud: Because it's sorted, I only need to compare with the last value I kept.