Remove Duplicates from Sorted Array II
Keep at most two copies of each value in place, using a read pointer and a write pointer
Problem Statement
Given a sorted integer array nums, remove duplicates in place so that each value appears at most twice. Return the new length k; the first k positions of nums must hold the result, and anything beyond k is ignored.
You must do this with O(1) extra memory.
Input: nums = [1, 1, 1, 2, 2, 3]
Output: 5, nums = [1, 1, 2, 2, 3, _]
Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]Intuition
Deleting from the middle of an array is expensive — every later element shifts left, giving O(n²).
The key insight
Do not delete. Rewrite.
Use two pointers over the same array:
readwalks every element, deciding what to keep.writemarks where the next kept element goes.
Because write never outpaces read, you always overwrite a slot you have already consumed. The array is rebuilt in place, in one pass.
The remaining question is how to decide whether to keep nums[read]. Since the array is sorted, all copies of a value sit together, so a local check suffices:
The at-most-two test
Keep nums[read] if write < 2 or nums[read] != nums[write - 2].
If the value two slots back in the output already equals the current value, then two copies are present and this would be a third. Otherwise it is the first or second copy, so keep it.
This generalises perfectly: change 2 to k and you have "at most k duplicates". With k = 1 it becomes the original Remove Duplicates problem.
Watch it run
Approach
Always keep the first two elements
While write < 2 there cannot be three copies yet, so the check is skipped.
Otherwise compare against nums[write - 2]
If they differ, this is at most the second copy → keep it. If they match, it is a third or later copy → skip.
Return write
It counts exactly how many elements were kept.
Compare against the output, not the input
The check must read nums[write - 2], not nums[read - 2]. Once elements start being skipped, the two pointers drift apart and nums[read - 2] points into the not-yet-rewritten region. Only the output prefix reflects what has actually been kept.
Solution
def remove_duplicates(nums: list[int]) -> int:
"""Keep at most two of each value in place; return the new length."""
write = 0
for value in nums:
# The first two slots are always safe; after that, compare with the
# value two positions back in the OUTPUT.
if write < 2 or value != nums[write - 2]:
nums[write] = value
write += 1
return writeGeneralised to at most k copies — the same code with one constant changed:
def remove_duplicates_k(nums: list[int], k: int = 2) -> int:
write = 0
for value in nums:
if write < k or value != nums[write - k]:
nums[write] = value
write += 1
return writeWhy iterating by value is safe here
for value of nums reads nums[read] before any write at that index could have happened, because write ≤ read always holds. If you are uneasy about reading and writing the same array in one loop, write the explicit index form — it is identical in behaviour.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass; each element is examined once and written at most once.
- Space — two integer pointers. No temporary array, satisfying the in-place requirement.
Edge Cases
Related Problems
- Merge Sorted Array — another in-place rewrite driven by a write pointer
- Middle of the Linked List — two pointers moving at different rates
- Valid Palindrome — two pointers on a string