Remove Duplicates from Sorted Array
Easy Read/write pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a sorted array, keep only one copy of each value at the front (in order) and return how many unique values there are. Do it in place.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: keep one copy of each value at the front, in place, and return how many unique values there are.
Why this works: in a sorted array duplicates are neighbours. The read pointer scans; the write pointer only moves when a new value appears.
Example: [1, 1, 2, 3, 3]
read 1 (dup) → skipread 2 → write at 1 → [1, 2, …]read 3 → write at 2 → [1, 2, 3, …]read 3 (dup) → skip; length 3
✦Hints open one at a time
↗Approach
write starts at 1. For each read index, if the value differs from the last written value, copy it to write and advance write. write is the new length.
</>Solution (Java)
class Solution {
public int removeDuplicates(int[] nums) {
int write = 1;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write - 1]) {
nums[write++] = nums[read]; // new unique value
}
}
return write;
}
}!Common mistake
Comparing nums[read] with nums[read - 1] after you've started overwriting — compare with nums[write - 1] to be safe.
- Time: O(n).
- Space: O(1).
