Read the problem description here.
This is a medium-range problem, and it genuinely pushed me to the edge. Even when I had a working solution in front of me, I couldn't reason about it. Then suddenly it clicked, and everything made perfect sense. I'm sharing my perspective partly to solidify my own understanding, and partly to help anyone else who is stuck. Let's jump in.
Here is our example array:
Your goal is to make it look like this:
You don't care what sits after the valid elements.
This problem is a variant of deduplicating a sorted array in-place, so make sure you understand that one first. The twist here: each value is allowed to appear at most twice.
Point No 1: The first two elements are always valid, no matter what they are. So the real processing starts at index 2.
We use two pointers: a readPointer that scans the array one value at a time, and a writePointer that tracks the next position in the clean array we are building. The readPointer always moves forward. The writePointer moves only after a successful write.
Both pointers start at index 2, because we already know the first two elements are valid.
The key question
Before every write, you ask the exact same question:
Can I write the readPointer's value into the writePointer's position?
If you can answer this correctly, you have solved the problem. So how do you answer it?
Ask what would make the array bad. Since each value may appear at most twice, a bad array is one where array[writePointer] === array[writePointer - 2] — three copies in a row. (If no duplicates were allowed at all, you would compare against writePointer - 1 instead. The "how many duplicates" rule directly decides how far back you look.)
So the answer is one comparison: the value you are about to write must differ from the value at writePointer - 2. If it differs, write it. If not, skip it.
Every step below asks this same question. Watch the pattern.
Walking through it
readPointer = 2, writePointer = 2. The value to write is 1. Look at writePointer - 2, which is 2 − 2 = index 0, holding the value 0. 1 ≠ 0, so the write is legal — write 1 at position 2. (The array looks unchanged, since we wrote the same value back, but the mechanism is working.) Both pointers move forward.
readPointer = 3, writePointer = 3. The value to write is 1. Look at writePointer - 2, which is 3 − 2 = index 1, holding the value 0. 1 ≠ 0, write is legal — write 1 at position 3. Both pointers move.
readPointer = 4, writePointer = 4. The value to write is 1. Look at writePointer - 2, which is 4 − 2 = index 2, holding the value 1. 1 === 1, equal! Writing would create three 1s in a row — a bad array. So we don't write.
Here is the interesting part. When you cannot write, only the readPointer moves. The writePointer stays, patiently holding its spot, because that position is still where the next valid value must go.
readPointer = 5, writePointer = 4. The value is again 1. Look at writePointer - 2, which is still 4 − 2 = index 2, holding 1. Equal again. Skip. We have now skipped two 1s back to back and the writePointer hasn't budged.
readPointer = 6, writePointer = 4. The value to write is 2. Look at writePointer - 2, which is 4 − 2 = index 2, holding 1. 2 ≠ 1, write is legal — write 2 at position 4.
This is the moment the array visibly changes. The third 1 at index 4 gets overwritten by 2:
The two pointers have now separated. From here on, the readPointer scouts ahead while the writePointer trails behind, building the clean array.
readPointer = 7, writePointer = 5. The value to write is 3. Look at writePointer - 2, which is 5 − 2 = index 3, holding 1. 3 ≠ 1, write is legal — write 3 at position 5.
readPointer = 8, writePointer = 6. The value to write is 3. Look at writePointer - 2, which is 6 − 2 = index 4, holding 2. 3 ≠ 2, write is legal — write 3 at position 6. Note that this second 3 is allowed because the comparison happens against the written region, not the original array. Two positions back in the clean part is 2, so the invariant automatically permits exactly one duplicate 3.
The readPointer has reached the end. We are done. The writePointer is 7, and that is the answer — the length of the valid array. The first 7 elements are [0, 0, 1, 1, 2, 3, 3], exactly what we wanted. Whatever garbage sits after index 6, we don't care.
The one question, generalized
Every iteration asks the same thing:
"Is the value I am reading different from the value at writePointer − 2?"
If yes, write it and move both pointers. If no, move only the readPointer. That's the entire algorithm — one comparison doing all the heavy lifting, guaranteeing no value ever appears a third time.
And if the problem ever changes to "allow at most k duplicates", you change the question to writePointer − k. Nothing else changes. That is the sign of a good invariant.
The code
export default function removeDuplicatesSortedArrayII(nums: number[]): number {
let readPointer = 0,
writePointer = 0;
for (; readPointer < nums.length; readPointer++) {
// can I write this value in the writePointer's position?
if (readPointer < 2 || nums[readPointer] !== nums[writePointer - 2]) {
nums[writePointer++] = nums[readPointer];
}
}
return writePointer;
}
The readPointer < 2 guard is Point No 1 from earlier: the first two elements are always valid, so they are written unconditionally. From index 2 onwards, the question kicks in. One pass, O(n) time, O(1) space.
What I learned the hard way
My first attempt tracked duplicates with a counter and tried to jump the writePointer around based on how many duplicates I had seen. It failed in two places: it destroyed the second valid copy whenever a new value appeared, and it never flushed trailing duplicates when the array ended mid-run. On paper, my brain was silently doing the right thing — but the code wasn't asking the right question.
The moment I reframed it as "can I write this value here, and how do I answer that?", everything collapsed into a single comparison. If you are stuck on this problem, don't memorize the solution. Ask the question.
Top comments (0)