Loading…

mediumArraysLC #80Frequently asked

Remove Duplicates from Sorted Array II

Q: How do you solve Remove Duplicates from Sorted Array II using the Explicit Run Counter (Intuitive First Pass) approach?

When to use it: Good to sketch first to show you understand the requirement, then refine to the look-back form. Don't present this as your final answer — it's wordier and error-prone at boundaries. Before the slick one-liner, it helps to write the requirement out literally: as you scan, remember which value you're currently in a run of, and how many copies of it you've already committed. Keep writing copies until you've placed two, then suppress the rest until a new value appears. **Why a counter feels natural but is fiddly.** The logic 'count up to 2, then reset on value change' is the direct reading of the problem, and it works. But it carries three pieces of state — the write pointer `k`, the previous value `prev`, and the run `count` — and the reset has to happen at exactly the right moment. Off-by-one bugs cluster around 'do I reset before or after writing?' and 'what's the initial count?'. It's correct, just heavier than it needs to be. **Why it's still worth saying out loud.** Verbalizing this version proves to the interviewer that you understand *what* must hold (no third copy) independent of the clever encoding. The optimal solution then lands as a simplification — you replace three variables with a single comparison — which reads as insight rather than memorization. **The bridge to the optimal.** Notice that `count` and `prev` together just answer one question: *would writing this element create a third identical copy?* On sorted data, that's answerable directly from the array we're already building — if the slot two back (`nums[k-2]`) holds the same value, we'd be making a third. That observation collapses all the bookkeeping into one condition. Time complexity: O(n). Space complexity: O(1).

LCPractice

Two Pointers · 15 of 30 · 9 min

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

In plain English

Compact the sorted array so no value appears more than twice, preserving order, and return the new length k. Because equal values sit next to each other, you only need to check whether adding the current element would create a third copy.

Examples

Example 1

Input: nums = [1, 1, 1, 2, 2, 3]
Output: 5, nums = [1, 1, 2, 2, 3, _]
Note: The third 1 is dropped. Each of 1, 2, 3 now appears at most twice; k = 5.

Example 2

Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
Note: Four 1s collapse to two; everything else already ≤ 2. k = 7.

Example 3

Input: nums = [1, 1, 1]
Output: 2, nums = [1, 1, _]
Note: Only two copies survive. k = 2.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order

Clarifying questions4First question: Is the input guaranteed sorted?Explore questions

Q1.Is the input guaranteed sorted?
Yes, non-decreasing. That's essential — it makes duplicates contiguous so a fixed-size look-back bounds each run. On unsorted input the look-back trick fails.
Q2.Must I preserve the relative order of the kept elements?
Yes (unlike Remove Element). The write pointer naturally preserves order since it copies left to right.
Q3.What about the elements after index k?
Don't-cares. The grader only inspects nums[0..k); leftover values past k are fine.
Q4.Could the array have just one element?
Yes, length ≥ 1. A single element is trivially fine — k = 1, and the k < 2 guard handles it.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Keep each value at most twice, in-place, and return the new length k. Because the array is sorted, duplicates are contiguous, so a single write pointer suffices: write nums[fast] only when k < 2 OR nums[fast] != nums[k-2]. That comparison against the element two slots back is the whole trick — it caps every run at two. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit sortedness to avoid counting structures, and whether you can express 'at most two' as a clean invariant on the write pointer rather than ad-hoc counters.

Where candidates slip

Comparing nums[fast] against nums[fast-1] in the original array (breaks once you start overwriting), or using a separate run-counter that mishandles the boundary between values.

How to stand out

State the nums[k-2] invariant and immediately generalize: 'for at most m, compare to nums[k-m]'. Note that sortedness is the assumption that makes a length-2 window sufficient.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Explicit Run Counter (Intuitive First Pass)	`O(n)`	`O(1)`	Good to sketch first to show you understand the requirement, then refine to the look-back form. Don't present this as your final answer — it's wordier and error-prone at boundaries.	Read
2	Write Pointer with Look-Back-by-2 (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with the invariant — 'keep nums[fast] iff it differs from nums[k-2]' — and mention it generalizes to nums[k-m] for 'at most m'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSorted array, cap copies per valueHow many copies are allowed?At most 1At most 2Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Explicit Run Counter (Intuitive First Pass)

TimeO(n)SpaceO(1)

Good to sketch first to show you understand the requirement, then refine to the look-back form. Don't present this as your final answer — it's wordier and error-prone at boundaries.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk the array and track the value of the current run and how many times you've already kept it. When do you write versus skip?

2Hint 2Explore hint

Keep a write pointer k, the previous value, and a count. If the current value equals the previous, increment count; otherwise reset count to 1.

3Hint 3Explore hint

Write the element only while count <= 2. Reset the counter whenever the value changes.

A · Core idea

Before the slick one-liner, it helps to write the requirement out literally: as you scan, remember which value you're currently in a run of, and how many copies of it you've already committed. Keep writing copies until you've placed two, then suppress the rest until a new value appears.

Why a counter feels natural but is fiddly. The logic 'count up to 2, then reset on value change' is the direct reading of the problem, and it works. But it carries three pieces of state — the write pointer k, the previous value prev, and the run count — and the reset has to happen at exactly the right moment. Off-by-one bugs cluster around 'do I reset before or after writing?' and 'what's the initial count?'. It's correct, just heavier than it needs to be.

Why it's still worth saying out loud. Verbalizing this version proves to the interviewer that you understand what must hold (no third copy) independent of the clever encoding. The optimal solution then lands as a simplification — you replace three variables with a single comparison — which reads as insight rather than memorization.

The bridge to the optimal. Notice that count and prev together just answer one question: would writing this element create a third identical copy? On sorted data, that's answerable directly from the array we're already building — if the slot two back (nums[k-2]) holds the same value, we'd be making a third. That observation collapses all the bookkeeping into one condition.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 1, 1, 2, 2, 3]

x=1 (i=0)

new value → count=1, write → nums[0]=1, k→1

Statek=1, count=1

Final resultk = 5, nums[0..5) = [1, 1, 2, 2, 3]

C · Code with teaching comments

Reference implementation previewpublic int removeDuplicates(int[] nums) { if (nums.length <= 2) return nums.length; int k = 0, count = 0; Integer prev = null; for (int x : nums) {Explore the full code

solution.javaJava

Explicit Run Counter (Intuitive First Pass) — reference

4 teaching notes

1
public int removeDuplicates(int[] nums) {
2
    // 0, 1, or 2 elements are already valid — nothing to remove.
3
    if (nums.length <= 2) return nums.length;
4
    int k = 0, count = 0;
5
    Integer prev = null;
6
    for (int x : nums) {
7
        if (prev != null && x == prev) {
8
            count++;
9
        } else {
10
            count = 1;
11
            prev = x;
12
        }
13
        if (count <= 2) {
14
            nums[k] = x;
15
            k++;
16
        }
17
    }
18
    return k;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The run counter and the previous-value tracker are redundant on sorted data — the array you're constructing already remembers both. Spotting that redundancy is the step from 'works' to 'elegant'.

ComplexityO(n) time, O(1) space — One pass, constant bookkeeping (k, prev, count) → O(n) time, O(1) space.

E · Edge cases and pitfalls5nums = [1, 1] — Length ≤ 2 short-circuit → return 2 unchanged.Explore edge cases

Edge cases handled

nums = [1, 1]Length ≤ 2 short-circuit → return 2 unchanged.
nums = [7]Length ≤ 2 → return 1.

Pitfalls

Forgetting to reset count to 1 (not 0) when the value changes — drops a legitimate copy.
Resetting prev but not count, or vice versa — desynchronizes the run state.
Initializing prev to a real value like nums[0] that could collide with a valid element instead of a sentinel.

03.2

Approach 2 of 2 · Optimal

Write Pointer with Look-Back-by-2 (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with the invariant — 'keep nums[fast] iff it differs from nums[k-2]' — and mention it generalizes to nums[k-m] for 'at most m'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array you're writing into is also sorted. If the element two slots back equals the current element, what does that tell you about how many copies you've already kept?

2Hint 2Explore hint

Maintain a write pointer k. Accept nums[fast] when k < 2 (first two slots always fit) or when nums[fast] != nums[k-2].

3Hint 3Explore hint

If nums[fast] == nums[k-2], the slots k-2 and k-1 already hold two copies of this value, so writing a third is forbidden — skip it.

A · Core idea

Because the input is sorted, the prefix we're building in nums[0..k) is also sorted. That lets us answer 'have I already kept two of this value?' by peeking at a single slot rather than maintaining counters.

The invariant, stated precisely. At all times, nums[0..k) is a valid answer for the elements processed so far — every value appears at most twice. To extend it with the current element x = nums[fast], we ask: would this create a third copy? Since the prefix is sorted, if x is going to collide it must collide with the largest values already kept, which live at nums[k-1] and nums[k-2]. If both equal x, then nums[k-2] == x, and accepting x would make three. So the accept rule is exactly `k < 2 || x != nums[k-2]`.

Why comparing to `nums[k-2]` and not `nums[fast-1]`. A tempting bug is to compare against the previous element in the original array. But we're overwriting nums as we go, so the original neighbors get clobbered — and more importantly, the count we care about is how many copies we've kept, which lives in the compacted prefix, not the raw input. The k-2 slot is the authoritative record of 'the second-most-recent value I committed'. If even that equals x, we're already at two.

Why `k < 2` comes first. For the first two writes there is no nums[k-2] to read (it'd be a negative index). Short-circuit evaluation makes k < 2 accept those unconditionally — the first two elements of any array are always allowed, since you can't exceed two copies with fewer than three slots filled. This also elegantly removes the need for the length-≤-2 special case the counter version needed.

Why it generalizes for free. Nothing about the value 2 is special. 'Keep at most m copies' becomes 'accept iff k < m or x != nums[k-m]'. The look-back distance is the multiplicity cap. Saying this in an interview signals you understand the structure, not just this instance.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]

Array state

fast=1

k<2 → accept second 1, k→2

[0]

fast ↓

[1]

k ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultk = 7, nums[0..7) = [0, 0, 1, 1, 2, 3, 3]

C · Code with teaching comments

solution.javaJava

Write Pointer with Look-Back-by-2 (Optimal) — optimal

4 teaching notes

1
public int removeDuplicates(int[] nums) {
2
    // Write pointer and final length; nums[0..k) is always a valid answer.
3
    int k = 0;
4
    for (int fast = 0; fast < nums.length; fast++) {
5
        // First two slots always fit; otherwise accept only if it won't be a third
6
        // copy.
7
        if (k < 2 || nums[fast] != nums[k - 2]) {
8
            // Commit the kept element and advance the write pointer.
9
            nums[k] = nums[fast];
10
            k++;
11
        }
12
    }
13
    // Number of kept elements; tail beyond k is ignored.
14
    return k;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

On sorted data, the compacted prefix is a self-documenting counter: nums[k-2] == x means 'two copies of x already committed'. Replace explicit counting with a fixed-distance look-back, and the offset equals the multiplicity you allow.

ComplexityO(n) time, O(1) space — Single pass with one comparison and at most one write per element → O(n) time. Only the write pointer k as extra state → O(1) space.

E · Edge cases and pitfalls6nums = [1, 1, 1] — First two accepted via k<2; third has nums[k-2]=nums[0]=1 → skip → k=2.Explore edge cases

Edge cases handled

nums = [1, 1, 1]First two accepted via k<2; third has nums[k-2]=nums[0]=1 → skip → k=2.
nums = [1, 2, 3]All distinct; every check passes → k=3, array unchanged.
nums = [5]Single element accepted via k<2 → k=1.

Pitfalls

Comparing nums[fast] to nums[fast-1] instead of nums[k-2] — wrong once overwriting begins.
Dropping the k < 2 guard — negative index into nums[-2] (Java throws, Python silently wraps).
Hard-coding 2 when the follow-up asks for m — remember the offset is the cap.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int removeDuplicates(int[] nums) { int k = 0; for (int fast = 0; fast < nums.length; fast++) { if (k < 2 || nums[fast] != nums[k - 2]) { nums[k] = nums[fast];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing to the wrong slot

nums[fast-1] reads the original (now possibly overwritten) array and tracks input adjacency, not how many copies you've KEPT. The authoritative count lives in the compacted prefix at nums[k-2].

Explore the code comparison

Don't write this

if (fast < 2 || nums[fast] != nums[fast - 2]) {
    nums[k++] = nums[fast];
}

Write this instead

if (k < 2 || nums[fast] != nums[k - 2]) {
    nums[k++] = nums[fast];
}

Missing the k < 2 short-circuit

Evaluating nums[k-2] when k is 0 or 1 reads nums[-2]/nums[-1]. Java throws ArrayIndexOutOfBounds; Python silently reads from the end and corrupts the logic.

Explore the code comparison

Don't write this

for fast in range(len(nums)):
    if nums[fast] != nums[k - 2]:
        nums[k] = nums[fast]
        k += 1

Write this instead

for fast in range(len(nums)):
    if k < 2 or nums[fast] != nums[k - 2]:
        nums[k] = nums[fast]
        k += 1

Resetting the run counter to 0 instead of 1

In the explicit-counter variant, a new value has already been seen once, so its count must start at 1. Resetting to 0 makes you keep three copies (0,1,2 all <= 2 before the cap kicks in).

Explore the code comparison

Don't write this

else:
    count, prev = 0, x

Write this instead

else:
    count, prev = 1, x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Write pointer with look-back-by-2 (sorted in-place dedupe)

Code pattern to memorize

k = 0
for x in nums:
    if k < 2 or x != nums[k - 2]:
        nums[k] = x
        k += 1
return k

Rules to remember

1Compare nums[fast] to nums[k-2], the last accepted slot's predecessor — not to nums[fast-1] in the original array.
2k < 2 short-circuits the first two writes so you never index nums[-2] / nums[-1].
3Sorted input is the load-bearing assumption — it makes equal values contiguous, so a length-2 look-back bounds the whole run.
4Generalises instantly: for 'keep at most m', compare to nums[k-m].
5Return k; the judge reads only nums[0..k) and ignores the tail.

Use this pattern when

Sorted array, cap each value at a fixed multiplicity in-place
O(1) extra space and the tail is throwaway
Any 'allow up to m copies' compaction on sorted data
Stable front-compaction where the kept order must match input

Choose another pattern when

Array is unsorted → sort first, or use a hash count (no longer O(1) space)
Need to remove ALL duplicates (keep one) → that's LC 26 with nums[k-1]
Need to keep a NEW array → no in-place benefit, just filter with a counter
Multiplicity varies per value → counting map, not a fixed look-back

Interview takeaway

When the array is sorted, 'at most m copies' becomes a one-line write-pointer rule: keep nums[fast] iff it differs from nums[k-m]. The sortedness turns a counting problem into a constant look-back — generalize the index offset and you've solved the whole family.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLook-back-by-m write pointer for in-place dedupe on sorted arrays. Recognise it whenever you must cap each value's multiplicity with O(1) space. The offset m is the cap: m = 1 is LC 26, m = 2 is this problem.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove Duplicates from Sorted Array
Keep at most one — compare to nums[k-1] (i.e., m = 1).
Remove Element
Same write-pointer skeleton, keep-condition is x != val instead of a look-back.
Move Zeroes
Write pointer collecting non-zeros, then pad the tail with zeros.
Duplicate Zeros
Coming soon
In-place rewrite — often done with a two-pass / right-to-left write pointer to avoid overwriting unread data.

Same pattern

←

H-Index

Continue · Next problem

Remove Element

mediumArraysLC #80Frequently asked

Remove Duplicates from Sorted Array II

LCPractice

Two Pointers · 15 of 30 · 9 min

Return k after placing the final result in the first k slots of nums.

In plain English

Examples

Example 1

Input: nums = [1, 1, 1, 2, 2, 3]
Output: 5, nums = [1, 1, 2, 2, 3, _]
Note: The third 1 is dropped. Each of 1, 2, 3 now appears at most twice; k = 5.

Example 2

Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
Note: Four 1s collapse to two; everything else already ≤ 2. k = 7.

Example 3

Input: nums = [1, 1, 1]
Output: 2, nums = [1, 1, _]
Note: Only two copies survive. k = 2.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order

Clarifying questions4First question: Is the input guaranteed sorted?Explore questions

Q1.Is the input guaranteed sorted?
Yes, non-decreasing. That's essential — it makes duplicates contiguous so a fixed-size look-back bounds each run. On unsorted input the look-back trick fails.
Q2.Must I preserve the relative order of the kept elements?
Yes (unlike Remove Element). The write pointer naturally preserves order since it copies left to right.
Q3.What about the elements after index k?
Don't-cares. The grader only inspects nums[0..k); leftover values past k are fine.
Q4.Could the array have just one element?
Yes, length ≥ 1. A single element is trivially fine — k = 1, and the k < 2 guard handles it.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit sortedness to avoid counting structures, and whether you can express 'at most two' as a clean invariant on the write pointer rather than ad-hoc counters.

Where candidates slip

Comparing nums[fast] against nums[fast-1] in the original array (breaks once you start overwriting), or using a separate run-counter that mishandles the boundary between values.

How to stand out

State the nums[k-2] invariant and immediately generalize: 'for at most m, compare to nums[k-m]'. Note that sortedness is the assumption that makes a length-2 window sufficient.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Explicit Run Counter (Intuitive First Pass)	`O(n)`	`O(1)`	Good to sketch first to show you understand the requirement, then refine to the look-back form. Don't present this as your final answer — it's wordier and error-prone at boundaries.	Read
2	Write Pointer with Look-Back-by-2 (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with the invariant — 'keep nums[fast] iff it differs from nums[k-2]' — and mention it generalizes to nums[k-m] for 'at most m'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Explicit Run Counter (Intuitive First Pass)

TimeO(n)SpaceO(1)

Good to sketch first to show you understand the requirement, then refine to the look-back form. Don't present this as your final answer — it's wordier and error-prone at boundaries.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk the array and track the value of the current run and how many times you've already kept it. When do you write versus skip?

2Hint 2Explore hint

Keep a write pointer k, the previous value, and a count. If the current value equals the previous, increment count; otherwise reset count to 1.

3Hint 3Explore hint

Write the element only while count <= 2. Reset the counter whenever the value changes.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 1, 1, 2, 2, 3]

x=1 (i=0)

new value → count=1, write → nums[0]=1, k→1

Statek=1, count=1

Final resultk = 5, nums[0..5) = [1, 1, 2, 2, 3]

C · Code with teaching comments

solution.javaJava

Explicit Run Counter (Intuitive First Pass) — reference

4 teaching notes

1
public int removeDuplicates(int[] nums) {
2
    // 0, 1, or 2 elements are already valid — nothing to remove.
3
    if (nums.length <= 2) return nums.length;
4
    int k = 0, count = 0;
5
    Integer prev = null;
6
    for (int x : nums) {
7
        if (prev != null && x == prev) {
8
            count++;
9
        } else {
10
            count = 1;
11
            prev = x;
12
        }
13
        if (count <= 2) {
14
            nums[k] = x;
15
            k++;
16
        }
17
    }
18
    return k;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The run counter and the previous-value tracker are redundant on sorted data — the array you're constructing already remembers both. Spotting that redundancy is the step from 'works' to 'elegant'.

ComplexityO(n) time, O(1) space — One pass, constant bookkeeping (k, prev, count) → O(n) time, O(1) space.

E · Edge cases and pitfalls5nums = [1, 1] — Length ≤ 2 short-circuit → return 2 unchanged.Explore edge cases

Edge cases handled

nums = [1, 1]Length ≤ 2 short-circuit → return 2 unchanged.
nums = [7]Length ≤ 2 → return 1.

Pitfalls

Forgetting to reset count to 1 (not 0) when the value changes — drops a legitimate copy.
Resetting prev but not count, or vice versa — desynchronizes the run state.
Initializing prev to a real value like nums[0] that could collide with a valid element instead of a sentinel.

03.2

Approach 2 of 2 · Optimal

Write Pointer with Look-Back-by-2 (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with the invariant — 'keep nums[fast] iff it differs from nums[k-2]' — and mention it generalizes to nums[k-m] for 'at most m'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array you're writing into is also sorted. If the element two slots back equals the current element, what does that tell you about how many copies you've already kept?

2Hint 2Explore hint

Maintain a write pointer k. Accept nums[fast] when k < 2 (first two slots always fit) or when nums[fast] != nums[k-2].

3Hint 3Explore hint

If nums[fast] == nums[k-2], the slots k-2 and k-1 already hold two copies of this value, so writing a third is forbidden — skip it.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]

Array state

fast=1

k<2 → accept second 1, k→2

[0]

fast ↓

[1]

k ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final resultk = 7, nums[0..7) = [0, 0, 1, 1, 2, 3, 3]

C · Code with teaching comments

solution.javaJava

Write Pointer with Look-Back-by-2 (Optimal) — optimal

4 teaching notes

1
public int removeDuplicates(int[] nums) {
2
    // Write pointer and final length; nums[0..k) is always a valid answer.
3
    int k = 0;
4
    for (int fast = 0; fast < nums.length; fast++) {
5
        // First two slots always fit; otherwise accept only if it won't be a third
6
        // copy.
7
        if (k < 2 || nums[fast] != nums[k - 2]) {
8
            // Commit the kept element and advance the write pointer.
9
            nums[k] = nums[fast];
10
            k++;
11
        }
12
    }
13
    // Number of kept elements; tail beyond k is ignored.
14
    return k;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Single pass with one comparison and at most one write per element → O(n) time. Only the write pointer k as extra state → O(1) space.

E · Edge cases and pitfalls6nums = [1, 1, 1] — First two accepted via k<2; third has nums[k-2]=nums[0]=1 → skip → k=2.Explore edge cases

Edge cases handled

nums = [1, 1, 1]First two accepted via k<2; third has nums[k-2]=nums[0]=1 → skip → k=2.
nums = [1, 2, 3]All distinct; every check passes → k=3, array unchanged.
nums = [5]Single element accepted via k<2 → k=1.

Pitfalls

Comparing nums[fast] to nums[fast-1] instead of nums[k-2] — wrong once overwriting begins.
Dropping the k < 2 guard — negative index into nums[-2] (Java throws, Python silently wraps).
Hard-coding 2 when the follow-up asks for m — remember the offset is the cap.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing to the wrong slot

nums[fast-1] reads the original (now possibly overwritten) array and tracks input adjacency, not how many copies you've KEPT. The authoritative count lives in the compacted prefix at nums[k-2].

Explore the code comparison

Don't write this

if (fast < 2 || nums[fast] != nums[fast - 2]) {
    nums[k++] = nums[fast];
}

Write this instead

if (k < 2 || nums[fast] != nums[k - 2]) {
    nums[k++] = nums[fast];
}

Missing the k < 2 short-circuit

Evaluating nums[k-2] when k is 0 or 1 reads nums[-2]/nums[-1]. Java throws ArrayIndexOutOfBounds; Python silently reads from the end and corrupts the logic.

Explore the code comparison

Don't write this

for fast in range(len(nums)):
    if nums[fast] != nums[k - 2]:
        nums[k] = nums[fast]
        k += 1

Write this instead

for fast in range(len(nums)):
    if k < 2 or nums[fast] != nums[k - 2]:
        nums[k] = nums[fast]
        k += 1

Resetting the run counter to 0 instead of 1

In the explicit-counter variant, a new value has already been seen once, so its count must start at 1. Resetting to 0 makes you keep three copies (0,1,2 all <= 2 before the cap kicks in).

Explore the code comparison

Don't write this

else:
    count, prev = 0, x

Write this instead

else:
    count, prev = 1, x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Write pointer with look-back-by-2 (sorted in-place dedupe)

Code pattern to memorize

k = 0
for x in nums:
    if k < 2 or x != nums[k - 2]:
        nums[k] = x
        k += 1
return k

Rules to remember

1Compare nums[fast] to nums[k-2], the last accepted slot's predecessor — not to nums[fast-1] in the original array.
2k < 2 short-circuits the first two writes so you never index nums[-2] / nums[-1].
3Sorted input is the load-bearing assumption — it makes equal values contiguous, so a length-2 look-back bounds the whole run.
4Generalises instantly: for 'keep at most m', compare to nums[k-m].
5Return k; the judge reads only nums[0..k) and ignores the tail.

Use this pattern when

Sorted array, cap each value at a fixed multiplicity in-place
O(1) extra space and the tail is throwaway
Any 'allow up to m copies' compaction on sorted data
Stable front-compaction where the kept order must match input

Choose another pattern when

Array is unsorted → sort first, or use a hash count (no longer O(1) space)
Need to remove ALL duplicates (keep one) → that's LC 26 with nums[k-1]
Need to keep a NEW array → no in-place benefit, just filter with a counter
Multiplicity varies per value → counting map, not a fixed look-back

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Remove Duplicates from Sorted Array
Keep at most one — compare to nums[k-1] (i.e., m = 1).
Remove Element
Same write-pointer skeleton, keep-condition is x != val instead of a look-back.
Move Zeroes
Write pointer collecting non-zeros, then pad the tail with zeros.
Duplicate Zeros
Coming soon
In-place rewrite — often done with a two-pass / right-to-left write pointer to avoid overwriting unread data.

Same pattern

←

H-Index

Continue · Next problem

Remove Element