LeetCode 80: Remove Duplicates from Sorted Array II

Problem Restatement

We are given an integer array nums sorted in non-decreasing order.

We need to remove extra duplicates in-place so that each unique number appears at most twice.

The relative order of the remaining numbers must stay the same.

The function returns k, where the first k elements of nums contain the final valid array. Values after index k - 1 do not matter.

The official problem states that each unique element may appear at most twice, the array must be modified in-place, and only O(1) extra memory may be used.

Input and Output

Function shape:

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        ...

Examples

Example 1:

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

The number 1 appears three times, so we keep only two copies.

The number 2 appears twice, so we keep both.

The number 3 appears once, so we keep it.

The final valid prefix is:

[1, 1, 2, 2, 3]

So the function returns:

5

After the function runs, nums may look like:

[1, 1, 2, 2, 3, _]

The last value does not matter.

Example 2:

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

Keep at most two copies of each number.

The valid prefix becomes:

[0, 0, 1, 1, 2, 3, 3]

The function returns:

7

First Thought: Count Groups

Because the array is sorted, equal values appear next to each other.

So one way is to process each group:

[1, 1, 1], [2, 2], [3]

For each group, we write:

min(2, group_size)

copies into the front of the array.

This works, but there is an even shorter method.

Key Insight

We write the result into the same array from left to right.

Let write be the position where the next kept number should go.

For every number num in nums, we decide whether it can be kept.

Since each value may appear at most twice, a new number can be written if either:

1. We have written fewer than two numbers so far.
2. num is different from the number two positions before write.

The key condition is:

if write < 2 or num != nums[write - 2]:

Why does this work?

If num == nums[write - 2], then the valid prefix already has two copies of num.

For example:

nums prefix = [1, 1]
write = 2
num = 1

Here:

nums[write - 2] = nums[0] = 1

So writing another 1 would create three copies.

But if:

num != nums[write - 2]

then adding num cannot create a third copy in the valid prefix.

Algorithm

Use one pointer:

write = 0

Then scan every number in nums.

For each num:

1. If write < 2, keep it.
2. Otherwise, compare num with nums[write - 2].
3. If they are different, write num at nums[write].
4. Increase write.
5. At the end, return write.

The first write elements are the valid answer.

Walkthrough

Use:

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

Start:

write = 0

Read first 1.

Since write < 2, keep it:

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

Read second 1.

Since write < 2, keep it:

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

Read third 1.

Now compare with nums[write - 2]:

nums[0] = 1
num = 1

They are equal, so skip this number.

Read 2.

Compare:

nums[0] = 1
num = 2

They are different, so keep 2:

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

Read second 2.

Compare:

nums[1] = 1
num = 2

They are different, so keep it:

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

Read 3.

Compare:

nums[2] = 2
num = 3

They are different, so keep it:

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

Return:

5

The valid prefix is:

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

Correctness

The algorithm maintains this invariant:

After processing some prefix of the original array, nums[:write] contains exactly the valid result for that processed prefix, with each value appearing at most twice.

At the beginning, write = 0, so the invariant is true.

When we read a new number num, there are two cases.

If write < 2, keeping num cannot create three copies of any value. So the valid prefix remains correct.

If write >= 2, we compare num with nums[write - 2].

Because the input array is sorted, equal values are processed consecutively. If num == nums[write - 2], then the valid prefix already contains two copies of num at the end. Writing another copy would violate the rule, so skipping it is correct.

If num != nums[write - 2], then adding num will not create a third copy. So writing it to nums[write] preserves the rule and keeps the relative order.

Thus the invariant remains true after every processed number.

When the scan finishes, nums[:write] is exactly the valid array after removing extra duplicates. Therefore, returning write is correct.

Complexity

Let:

n = len(nums)

Implementation

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        write = 0

        for num in nums:
            if write < 2 or num != nums[write - 2]:
                nums[write] = num
                write += 1

        return write

Code Explanation

We start with:

write = 0

This points to the next position where we can write a kept value.

Then we scan the array:

for num in nums:

The condition decides whether num can remain in the final prefix:

if write < 2 or num != nums[write - 2]:

The write < 2 part keeps the first two values automatically.

The second part checks whether writing num would create a third copy.

If the number is allowed, we write it:

nums[write] = num

Then move the write pointer:

write += 1

At the end, write is the length of the valid prefix:

return write

Testing

LeetCode checks both the returned length and the first k elements.

def check(nums, expected):
    s = Solution()
    k = s.removeDuplicates(nums)

    assert k == len(expected)
    assert nums[:k] == expected

def run_tests():
    check([1, 1, 1, 2, 2, 3], [1, 1, 2, 2, 3])
    check([0, 0, 1, 1, 1, 1, 2, 3, 3], [0, 0, 1, 1, 2, 3, 3])
    check([1], [1])
    check([1, 1], [1, 1])
    check([1, 1, 1], [1, 1])
    check([1, 2, 3], [1, 2, 3])
    check([], [])

    print("all tests passed")

run_tests()

Test meaning: