Remove Duplicates from Sorted Array II (LeetCode 80)
You're given an already-sorted (smallest to largest) integer array nums. Trim it in-place so no value shows up more than twice, while keeping the surviving values in their original relative order.
Some languages can't resize an array in place, so instead pack the surviving values into the front of nums. Concretely: if k values remain after the trim, the first k slots of nums must hold them — whatever sits past that point is ignored.
Return that count k once the first k slots of nums hold the final result.
You must do this without allocating another array — only extra memory, modifying nums directly.
Custom Judge:
We compare the k you return with the length of the expected trimmed array, then check that each of the first k slots of nums holds the expected value for that position. Anything after slot k - 1 is ignored.
Worked Examples
nums = [1,1,1,2,2,3]5, nums = [1,1,2,2,3,_]nums = [0,0,1,1,1,1,2,3,3]7, nums = [0,0,1,1,2,3,3,_,_]⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
Core Insight
Comparing candidate elements against nums[writer - 2] directly enforces the at-most-2 invariant without needing auxiliary counters.
Real-World Scenario & Production Applications
Memory compaction with bounded frequency quotas, rate-limiting transaction buffers, and bounded-run compression.
Subproblems & Recurrence Decomposition3 Phases
slow tracks the next write position; the first two elements are always kept unconditionally since any value is allowed to appear at least twice.
slow = 2 # first 2 elements are always keptStep-by-Step Execution Trace Table
| Step | reader | nums[reader] | nums[writer - 2] | Action | Mutated Array Prefix | writer |
|---|---|---|---|---|---|---|
| init | — | — | — | Keep first 2 elements automatically | [1, 1, ...] | 2 |
| 1 | 2 | 1 | 1 | 3rd duplicate (1 == 1) skip | [1, 1, ...] | 2 |
| 2 | 3 | 2 | 1 | Novel element (2 != 1) nums[2] = 2, writer++ | [1, 1, 2, ...] | 3 |
| 3 | 4 | 2 | 1 | 2nd copy of 2 (2 != 1) nums[3] = 2, writer++ | [1, 1, 2, 2, ...] | 4 |
| 4 | 5 | 3 | 2 | Novel element (3 != 2) nums[4] = 3, writer++ | [1, 1, 2, 2, 3] | 5 |
| 1 | if len(nums) <= 2: |
| 2 | return len(nums) |
| 3 | writer = 2 |
| 4 | for reader in range(2, len(nums)): |
| 5 | if nums[reader] != nums[writer - 2]: |
| 6 | nums[writer] = nums[reader] |
| 7 | writer += 1 |
| 8 | return writer |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When deduplication rules relax from "at most 1" to "at most " duplicates (here ), many reach for counter dictionaries or state variables. The Reader-Writer pattern solves this universally with zero additional variables.
🏆 The Core Invariant: The Kept-Prefix Boundary
The kept prefix nums[0..writer-1] is your certified result so far. If you allow at most duplicates, the earliest copy of the current number you could have kept is at writer - k.
Because the array is sorted, any element equal to nums[writer - k] has already reached its quota of copies in the output prefix.
🏷️ The Analogy: A VIP Room with a Strict 2-Guest Limit
Imagine a VIP lounge where each guest type can bring at most 2 friends. The bouncer (writer) admits the first 2 guests unconditionally (writer = 2). For every subsequent person in line (reader), the bouncer doesn't need a clipboard. Because guests arrive grouped by type (sorted array), the bouncer simply looks at the guest admitted two slots ago (writer - 2). If the current person matches, the 2-person quota is full! If they differ, admission is granted: write nums[writer] = nums[reader] and advance writer.
🔑 Why It Works
If nums[reader] == nums[writer - 2], then since the array is sorted, nums[writer - 1] is also equal to nums[reader]. Adding nums[reader] would create a 3rd duplicate! Skipping it preserves the at-most-2 invariant automatically.
Comparing against
reader - 2instead ofwriter - 2: When allowing at most duplicates, you must compare the incoming candidatenums[reader]against the finalized element committed two slots ago (nums[writer - 2]). Comparing againstreader - 2gets fooled by runs of 3+ duplicates.Premature loop start index: The first 2 elements (indices 0 and 1) are always valid regardless of values. The loop must initialize
writer = 2and scanreaderfrom index 2.Returning
writer + 1instead ofwriter: Becausewriteris zero-indexed and points to the next available slot, its value directly equals the number of preserved elements.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + in-place modification + allow up to k duplicates + O(1) memory requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: nums[0..writer-1] contains the sorted elements with at most 2 occurrences each. If nums[reader] != nums[writer-2], nums[writer] = nums[reader] and writer increments.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using counter variables and reset flags instead of looking back into the trusted kept array.
Boundary check failure when len(nums) <= 2: guard
if len(nums) <= 2: return len(nums).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize writer = 2 since the first two elements are always valid. The reader scans from index 2; whenever nums[reader] differs from nums[writer-2], we have not yet exceeded our quota of two duplicates, so I write at nums[writer] and increment writer. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Reader pointer scans each element exactly once from index 2 to N-1; writer pointer writes at most N times in-place. Total operations are strictly linear in N.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only two scalar integer pointers (reader, writer) are stored in constant memory.
T(N) = O(N)
Derivation Progression
for reader in range(2, N)
Reader pointer visits elements starting from index 2 to end exactly once.
if nums[reader] != nums[writer - 2]: nums[writer] = nums[reader], writer++
Writer advances strictly when candidate does not exceed the quota of 2 duplicates.
O(N) total steps
Array is mutated in-place with zero heap allocations.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative
O(1) Zero heap allocations
O(1) Returns integer count
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "at most twice", "in-place with O(1) extra memory". Generalized -duplicate compaction problem (). Instead of comparing candidate nums[read] with immediately preceding element, compare it against the element written steps ago (nums[write - k]).
. Requires time and space. Boundary choice: if , every element is valid; write pointer starts at index 2.
Comparing against read - 2 checks the raw unsifted input array, which allows duplicate runs of length if writes lag behind reads. Must always compare against the compacted output buffer nums[write - 2].
Remove Duplicates from Sorted Array II (LeetCode 80)
You're given an already-sorted (smallest to largest) integer array nums. Trim it in-place so no value shows up more than twice, while keeping the surviving values in their original relative order.
Some languages can't resize an array in place, so instead pack the surviving values into the front of nums. Concretely: if k values remain after the trim, the first k slots of nums must hold them — whatever sits past that point is ignored.
Return that count k once the first k slots of nums hold the final result.
You must do this without allocating another array — only extra memory, modifying nums directly.
Custom Judge:
We compare the k you return with the length of the expected trimmed array, then check that each of the first k slots of nums holds the expected value for that position. Anything after slot k - 1 is ignored.
Worked Examples
nums = [1,1,1,2,2,3]5, nums = [1,1,2,2,3,_]nums = [0,0,1,1,1,1,2,3,3]7, nums = [0,0,1,1,2,3,3,_,_]⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
Core Insight
Comparing candidate elements against nums[writer - 2] directly enforces the at-most-2 invariant without needing auxiliary counters.
Real-World Scenario & Production Applications
Memory compaction with bounded frequency quotas, rate-limiting transaction buffers, and bounded-run compression.
Subproblems & Recurrence Decomposition3 Phases
slow tracks the next write position; the first two elements are always kept unconditionally since any value is allowed to appear at least twice.
slow = 2 # first 2 elements are always keptStep-by-Step Execution Trace Table
| Step | reader | nums[reader] | nums[writer - 2] | Action | Mutated Array Prefix | writer |
|---|---|---|---|---|---|---|
| init | — | — | — | Keep first 2 elements automatically | [1, 1, ...] | 2 |
| 1 | 2 | 1 | 1 | 3rd duplicate (1 == 1) skip | [1, 1, ...] | 2 |
| 2 | 3 | 2 | 1 | Novel element (2 != 1) nums[2] = 2, writer++ | [1, 1, 2, ...] | 3 |
| 3 | 4 | 2 | 1 | 2nd copy of 2 (2 != 1) nums[3] = 2, writer++ | [1, 1, 2, 2, ...] | 4 |
| 4 | 5 | 3 | 2 | Novel element (3 != 2) nums[4] = 3, writer++ | [1, 1, 2, 2, 3] | 5 |
| 1 | if len(nums) <= 2: |
| 2 | return len(nums) |
| 3 | writer = 2 |
| 4 | for reader in range(2, len(nums)): |
| 5 | if nums[reader] != nums[writer - 2]: |
| 6 | nums[writer] = nums[reader] |
| 7 | writer += 1 |
| 8 | return writer |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
When deduplication rules relax from "at most 1" to "at most " duplicates (here ), many reach for counter dictionaries or state variables. The Reader-Writer pattern solves this universally with zero additional variables.
🏆 The Core Invariant: The Kept-Prefix Boundary
The kept prefix nums[0..writer-1] is your certified result so far. If you allow at most duplicates, the earliest copy of the current number you could have kept is at writer - k.
Because the array is sorted, any element equal to nums[writer - k] has already reached its quota of copies in the output prefix.
🏷️ The Analogy: A VIP Room with a Strict 2-Guest Limit
Imagine a VIP lounge where each guest type can bring at most 2 friends. The bouncer (writer) admits the first 2 guests unconditionally (writer = 2). For every subsequent person in line (reader), the bouncer doesn't need a clipboard. Because guests arrive grouped by type (sorted array), the bouncer simply looks at the guest admitted two slots ago (writer - 2). If the current person matches, the 2-person quota is full! If they differ, admission is granted: write nums[writer] = nums[reader] and advance writer.
🔑 Why It Works
If nums[reader] == nums[writer - 2], then since the array is sorted, nums[writer - 1] is also equal to nums[reader]. Adding nums[reader] would create a 3rd duplicate! Skipping it preserves the at-most-2 invariant automatically.
Comparing against
reader - 2instead ofwriter - 2: When allowing at most duplicates, you must compare the incoming candidatenums[reader]against the finalized element committed two slots ago (nums[writer - 2]). Comparing againstreader - 2gets fooled by runs of 3+ duplicates.Premature loop start index: The first 2 elements (indices 0 and 1) are always valid regardless of values. The loop must initialize
writer = 2and scanreaderfrom index 2.Returning
writer + 1instead ofwriter: Becausewriteris zero-indexed and points to the next available slot, its value directly equals the number of preserved elements.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + in-place modification + allow up to k duplicates + O(1) memory requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: nums[0..writer-1] contains the sorted elements with at most 2 occurrences each. If nums[reader] != nums[writer-2], nums[writer] = nums[reader] and writer increments.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using counter variables and reset flags instead of looking back into the trusted kept array.
Boundary check failure when len(nums) <= 2: guard
if len(nums) <= 2: return len(nums).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize writer = 2 since the first two elements are always valid. The reader scans from index 2; whenever nums[reader] differs from nums[writer-2], we have not yet exceeded our quota of two duplicates, so I write at nums[writer] and increment writer. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Reader pointer scans each element exactly once from index 2 to N-1; writer pointer writes at most N times in-place. Total operations are strictly linear in N.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only two scalar integer pointers (reader, writer) are stored in constant memory.
T(N) = O(N)
Derivation Progression
for reader in range(2, N)
Reader pointer visits elements starting from index 2 to end exactly once.
if nums[reader] != nums[writer - 2]: nums[writer] = nums[reader], writer++
Writer advances strictly when candidate does not exceed the quota of 2 duplicates.
O(N) total steps
Array is mutated in-place with zero heap allocations.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative
O(1) Zero heap allocations
O(1) Returns integer count
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "at most twice", "in-place with O(1) extra memory". Generalized -duplicate compaction problem (). Instead of comparing candidate nums[read] with immediately preceding element, compare it against the element written steps ago (nums[write - k]).
. Requires time and space. Boundary choice: if , every element is valid; write pointer starts at index 2.
Comparing against read - 2 checks the raw unsifted input array, which allows duplicate runs of length if writes lag behind reads. Must always compare against the compacted output buffer nums[write - 2].