Remove Duplicates from Sorted Array II
Medium · Two Pointers · Array · Two Pointers
Problem
You are given an integer array nums sorted in non-decreasing order. Edit it in place so that each distinct value appears at most twice, keeping the relative order of what remains, and return k, the number of elements kept.
The first k positions of nums must hold the result, in order; whatever is left after them is ignored. Use O(1) extra memory: do not build a second array.
The grader checks the returned k and nums[:k].
Examples
Input: nums = [1,1,1,2,3,3,3,3] Output: k = 5, nums[:5] = [1,1,2,3,3]
The run of three 1s and the run of four 3s are each cut to two copies. The 2 stays.
Input: nums = [4,5,6] Output: k = 3, nums[:3] = [4,5,6]
No value appears more than twice, so nothing moves.
Input: nums = [9,9,9] Output: k = 2, nums[:2] = [9,9]
The third 9 is dropped. What sits in nums[2] afterwards does not matter.
Constraints
- 1 <= len(nums) <= 3 · 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order
Approaches
- Delete each extra copy by shifting — time O(n²), space O(1)
Follow-up
What if each value may appear at most m times? Compare with nums[k - m] instead of nums[k - 2]; the proof is the same. And if the array were not sorted, copies would no longer be adjacent, so you would need a count per value (a hash map) and the order of first appearances.
Related problems
Start free on Cariara · Coding problems · System design studio
