Remove Duplicates from Sorted Array II
Given a sorted array nums, remove duplicates in-place so that each element appears at most twice, and return the new length.
- 1 <= nums.length <= 3 * 10⁴
- -10⁴ <= nums[i] <= 10⁴
- nums is sorted in non-decreasing order.
Intuition
Remove duplicates from sorted array ii allows each value to appear at most twice, rather than once. The structure is identical to the original problem, and one change adapts it.
In the original, each candidate is compared against nums[write − 1] — the most recently written value. Allowing two copies means looking back one position further:
- Compare against nums[write − 2], the value written two positions ago; if they differ, at most one copy of the current value has been kept and another is allowed.
The reasoning is direct. If the element two slots back differs from the current value, then at most one copy of it sits in the output, so a second is permitted. If they match, two copies are already present and this one is skipped.
The write pointer starts at 2, since the first two elements are always acceptable regardless of whether they are equal — two copies is the limit, not a violation.
That starting value also protects the write − 2 index from going negative, which is why no bounds check is needed inside the loop.
Arrays shorter than three elements are returned unchanged with their own length, since no value can appear more than twice in two slots. This falls out naturally when the loop starts at index 2 and does not run.
The generalisation is worth seeing: allowing k copies means comparing against nums[write − k] and starting the write pointer at k. The original problem is k = 1 and this one is k = 2, from the same three lines of code.
One pass with two indices gives O(n) time and O(1) space.
When a sorted array asks you to remove excess duplicates in-place (allowing at most k copies), the pattern is a single write pointer that checks against the element k positions back. The comparison nums[write - k] is the universal guard. For 'at most 1' it becomes the classic remove-duplicates problem; for 'at most 2' it is this problem.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n) time and O(1) space.
Adapt the original comparison
The single-copy version compares against nums[write - 1]. Allowing two copies means looking back one position further.
Compare two positions back
Test nums[read] != nums[write - 2]. A difference means at most one copy is present, so another is allowed; a match means two are already there.
Start the write pointer at two
The first two elements are always acceptable, even when equal — two copies is the limit, not a violation. Starting at 2 also keeps write - 2 non-negative.
Skip the bounds check
Because the write pointer begins at 2, the write - 2 index is never negative. No guard is needed inside the loop.
Return short arrays unchanged
Arrays of fewer than three elements cannot violate the rule, and the loop simply does not run — the length is returned as-is.
See the generalisation
Allowing k copies means comparing against nums[write - k] and starting at k. The original problem is k = 1, this one k = 2, from identical code.
Cost of the approach
One pass with two indices gives O(n) time and O(1) space, modifying the array in place.
Solution & live demo
Common pitfalls
Comparing against the read pointer's position instead of the write pointer's
if i < 2 or nums[i] != nums[i - 2]:
if write < 2 or nums[i] != nums[write - 2]:
Comparing nums[i] with nums[i - 2] checks the original array, not the accepted region. If three identical values sit in a row, the third compares against the first (which differs by position, not value) and may be wrongly accepted. The write pointer tracks the cleaned array.
Starting the write pointer at 2 and skipping the copy for the first two
write = 2 for i in range(2, len(nums)):
write = 0 for i in range(len(nums)):
Starting at 2 assumes the first two elements are always valid to keep in place. This is true for this problem, but the approach is fragile — if the array is empty or length 1, starting at 2 overshoots. The unified loop with write < 2 handles all lengths.
Forgetting to actually copy the element before advancing write
if write < 2 or nums[i] != nums[write - 2]:
write += 1if write < 2 or nums[i] != nums[write - 2]:
nums[write] = nums[i]
write += 1Without the copy, nums[write] still holds whatever was there originally. Once a skipped element separates i from write, the accepted region has stale values. The copy is what makes the in-place modification work.
Edge cases
The write < 2 condition accepts all of them. An array of length 0, 1, or 2 is returned unchanged.
[1,1,1,1]The first two are accepted (write < 2). Every subsequent element matches nums[write - 2], so it is skipped. Result length is 2.
Every element differs from nums[write - 2], so all are accepted. The result is the original array.