Remove duplicates from sorted array ii is a classic interview problem that asks you to modify a sorted integer array in‑place so that each distinct value appears at most twice. This concise meta description captures the core task, the required in‑place modification, and the “at most twice” constraint, making it clear for both beginners and experienced programmers.
Understanding the Problem
The input is a sorted array nums. The goal is to keep up to two occurrences of each number while removing any additional copies. Because the array is sorted, duplicate values are grouped together. The operation must be performed in‑place, meaning you cannot allocate another array of size n; only a constant amount of extra memory (O(1)) is allowed. The function should return the new length of the array after duplicates have been removed, and the first k elements of nums (where k is the returned length) must contain the valid result.
Honestly, this part trips people up more than it should.
Key constraints to remember:
- Sorted → duplicates are contiguous.
- At most twice → each distinct value may appear 1 or 2 times.
- In‑place → modify the original array, no extra storage proportional to n.
- Return length → the number of elements that are kept.
Approach Overview
The most efficient way to satisfy these constraints is to use the two‑pointer technique. Because the array is sorted, we can decide whether to keep the current element by looking at the element located two positions before slow. Now, one pointer (slow) tracks the position where the next valid element should be placed, while another pointer (fast) scans through the array to inspect each element. If the current element is different from that reference, it means we have seen it fewer than two times, so we can safely write it to slow and advance the slow pointer.
Easier said than done, but still worth knowing.
This approach yields:
- Time complexity: O(n), where n is the length of the array, since each element is examined once.
- Space complexity: O(1), as only a few integer variables are used.
Step‑by‑Step Solution
Using Two Pointers
-
Initialize pointers
slow = 0– the index where the next kept element will be written.fast = 0– the scanning index that traverses the whole array.
-
Iterate while
fastis within bounds- If
fast < 2, we can always keep the element because there are not yet two previous elements to compare against. - Otherwise, compare
nums[fast]withnums[slow‑2].- If they are different, the current element has appeared fewer than two times, so we keep it:
nums[slow] = nums[fast]. - If they are the same, the element would exceed the allowed two occurrences, so we skip it.
- If they are different, the current element has appeared fewer than two times, so we keep it:
- If
-
Advance pointers
- Increment
fastafter each iteration. - Increment
slowonly when an element is kept (i.e., when we write it tonums[slow]).
- Increment
-
Return the result
- The new length is
slow + 1(becauseslowis zero‑based).
- The new length is
Edge Cases
- Empty array → return 0; nothing to process.
- Array with 1 or 2 elements → all elements are valid; return the array length unchanged.
- All elements identical → only the first two are retained; the rest are ignored.
- No duplicates → the array remains unchanged; the returned length equals the original length.