#80
Remove Duplicates from Sorted Array II
Medium Read/write pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a sorted array, keep at most two copies of each value at the front, in place, and return the new length.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: keep at most two copies of each value.
Why this works: a value may be written if it differs from the value two places behind the write pointer.
Example: [1, 1, 1, 2, 2, 3]
write 1, 1third 1 = nums[write-2] → skipwrite 2, 2, 3 → [1, 1, 2, 2, 3]
✦Hints open one at a time
Same write-pointer idea as the "one copy" version.
A value can be written if it differs from the element two places behind the write position.
↗Approach
For each value x, write it if write < 2 or x != nums[write - 2]. Comparing with two slots back allows exactly two copies.
</>Solution (Java)
class Solution {
public int removeDuplicates(int[] nums) {
int write = 0;
for (int x : nums) {
if (write < 2 || x != nums[write - 2]) nums[write++] = x;
}
return write;
}
}!Common mistake
Comparing with nums[read - 2] instead of nums[write - 2] — the read side still contains the extra copies.
Complexity
- Time: O(n).
- Space: O(1).
