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.
Intuition
Because the array is sorted, all copies of a value are consecutive. You need a write pointer that decides whether to accept the next element. The rule is simple: accept the element if the position you are about to write is less than 2 (the first two elements are always safe), or if the element differs from the one two positions back in the accepted region. That single comparison — nums[i] != nums[write - 2] — enforces the 'at most two' invariant without counting duplicates or tracking the current run length.
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
Set up a write pointer starting at the beginning
Use a variable write (starting at 0) to mark where the next accepted element will go. Everything to the left of write is the cleaned portion of the array. A separate read pointer i scans through the original array.
Accept an element when it doesn't violate the at-most-two rule
For each element nums[i], check: is write < 2, or is nums[i] != nums[write - 2]? If either condition holds, copy nums[i] to nums[write] and advance write. The first condition lets the first two elements through unconditionally. The second condition compares against the element two positions back in the accepted region — if they match, the current value already appears twice and must be skipped.
Return `write` as the new length
After scanning all elements, write is the count of accepted elements, and nums[0..write-1] holds the result. Time is O(n) for the single pass, space is O(1) since we modify in place.
Solution
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.