#80 Remove Duplicates from Sorted Array II

frequently reported atAmazon Meta Bloomberg Microsoft

the problem

In plain words

nums is sorted in non-decreasing order. In place, keep at most two copies of each value, in the original order. Return k, the length of the result; nums[0..k) must hold it. Use O(1) extra memory.

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

out 5, nums = [1,1,2,2,3,_]

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

out 7, nums = [0,0,1,1,2,3,3,_,_]

1 ≤ n ≤ 3·10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Sorted non-decreasing

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (read / write)

A value may be kept if it differs from the value two slots back in the kept part, nums[write − 2]. Because the array is sorted, that one comparison tells you whether two copies are already in.

solutions

From brute force to optimal

Count how many times the current value has appeared; copy only the first two of each run into a list, then write the list back.

run = 1 when the value changes, else run + 1.
If run ≤ 2, add the value to a list.
Copy the list back into nums; return its size.

timeO(n)

Two linear passes.

spaceO(n)

The extra list — the problem asks for O(1).

javajava.util.*

1class Solution {2    public int removeDuplicates(int[] nums) {3        List<Integer> keep = new ArrayList<>();4        int run = 0;                                       // copies of the current value seen so far5        for (int i = 0; i < nums.length; i++) {6            run = (i > 0 && nums[i] == nums[i - 1]) ? run + 1 : 1;7            if (run <= 2) keep.add(nums[i]);               // first two copies of each value8        }9        for (int i = 0; i < keep.size(); i++) nums[i] = keep.get(i);10        return keep.size();11    }12}

Keep x unless the last two kept values are already x.

write = 0.
For each x: if write < 2 or x != nums[write − 2], nums[write++] = x.
Return write.

timeO(n)

One pass.

spaceO(1)

In place.

javajava.util.*

1class Solution {2    public int removeDuplicates(int[] nums) {3        int write = 0;4        for (int x : nums) {5            // keep x unless the last two kept values are already x (sorted, so nums[write - 2] == x says it all)6            if (write < 2 || x != nums[write - 2]) nums[write++] = x;7        }8        return write;9    }10}

in the room

How to say it in the interview

talk track

Start from LC 26 (compare with nums[write − 1]) and generalise: "at most k copies → compare with nums[write − k]".
Say why it compares with the kept part and not with nums[read − 2]: that original slot may already be overwritten.

traps

Comparing with nums[read − 2] — that slot may already be overwritten. Compare with nums[write − 2].
Counting runs but forgetting to reset the counter when the value changes.

what they ask next

Follow-ups

At most k copies?

Same loop with write < k || x != nums[write − k]. k = 1 is LC 26.

before you submit

Edge cases to test

One or two elements: always kept → k = n.
A run of three or more, [7, 7, 7] → [7, 7].
All values distinct → nothing removed.
Comparing with nums[read − 2] fails on [1, 1, 1, 2, 2, 2, 3]: an overwritten slot hides the second 2.

practise next