1. Problem Statement (Simple Explanation)
You’re given a sorted integer array nums (non-decreasing).
You must:
Remove extra duplicates in-place so that each unique value appears at most twice.
Keep the relative order of elements.
Put the result in the first k positions of nums.
Return k (the new length).
Anything beyond index k-1 can be ignored.
Constraints:
Do it in-place, O(1) extra memory.
nums length up to 3 * 104.
2. Examples
Example 1:
Input: nums = [1,1,1,2,2,3]
Allowed counts: at most 2 of each number.
Output:
k = 5
nums becomes [1,1,2,2,3,_] (the _ denote “don’t care”).
Explanation:
1 appears 3 times → keep 2.
2 appears 2 times → keep 2.
3 appears 1 time → keep 1.
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output:
k = 7
First 7 elements: [0,0,1,1,2,3,3,_,_]
Explanation:
0 → keep [0,0]
1 → originally 4 times, keep only [1,1]
2 → once
3 → twice
3. Approach – Two-pointer “Write Index” Pattern (O(n), O(1))
Because nums is sorted, duplicates are grouped.
We want:
For each value, allow up to 2 copies.
Extra copies (>2) must be skipped.
We use a single pass with a write index k:
k = length of processed part (next position to write).
Iterate i over all indices in nums:
If k < 2, we can always copy nums[i]:
We don’t have 2 elements yet.
Else (we already have at least 2 elements in result):
Compare nums[i] with nums[k - 2]:
If nums[i] != nums[k - 2], it means the new number is different from the element two spots before, so it is either:
a new value, or
the second occurrence of this value. Both are allowed.
If nums[i] == nums[k - 2], it means we already have two copies of this value in the result → skip this nums[i].
If accepted, assign:
nums[k] = nums[i]
k++
At the end, k is the new length.
Pseudo-code:
Why does nums[k-2] check work?
For each value:
The first two occurrences:
When k < 2, we just copy.
After that, if we get the 3rd copy, then nums[i] == nums[k-2] will be true (since the last two kept are same value).
So we skip the 3rd and all subsequent.
Complexity:
Let n = len(nums):
Time: O(n) – single pass.
Extra space: O(1) – in-place.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment