Keep At Most Two Copies
MediumTwo Pointers
Problem
An inventory export nums is sorted in non-decreasing order, but some item codes repeat many times. Compact it so that every code appears at most twice, keeping the sorted order.
Do the compaction in place with O(1) extra memory, then return the compacted prefix (the first k elements, where k is the new length).
Example 1
- Input:
- nums = [1, 1, 1, 2, 3, 3, 3, 3]
- Output:
- [1, 1, 2, 3, 3]
The third 1 and the third and fourth 3 are dropped.
Example 2
- Input:
- nums = [4, 5, 6]
- Output:
- [4, 5, 6]
Constraints
- 0 ≤ nums.length ≤ 3·10^4
- -10^4 ≤ nums[i] ≤ 10^4
- nums is sorted in non-decreasing order
Hint
Show the first hint
Because the array is sorted, all copies of a value are adjacent.
Walkthrough
How to approach it
01Clarify before coding
- What exactly is returned? The kept prefix nums[0..k), after compacting in place.
- Is the input always sorted? Yes, which means equal values are contiguous.
- Can the array be empty? Yes: return an empty list.
02Brute force
Count occurrences in a map and rebuild the list with min(count, 2) copies of each value; or delete extra copies one by one with list deletion.
Cost: The map uses O(n) extra memory; repeated deletion is O(n²) time because each deletion shifts the tail.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.