# 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

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | Integer `k`, the length of the valid prefix |
| Mutation | Modify `nums` in-place |
| Rule | Each unique value may appear at most twice |
| Order | Preserve the original relative order |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
[1, 1, 2, 2, 3]
```

So the function returns:

```python
5
```

After the function runs, `nums` may look like:

```python
[1, 1, 2, 2, 3, _]
```

The last value does not matter.

Example 2:

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

Keep at most two copies of each number.

The valid prefix becomes:

```python
[0, 0, 1, 1, 2, 3, 3]
```

The function returns:

```python
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:

```python
[1, 1, 1], [2, 2], [3]
```

For each group, we write:

```python
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:

```python
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:

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

Here:

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

So writing another `1` would create three copies.

But if:

```python
num != nums[write - 2]
```

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

## Algorithm

Use one pointer:

```python
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:

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

Start:

```python
write = 0
```

Read first `1`.

Since `write < 2`, keep it:

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

Read second `1`.

Since `write < 2`, keep it:

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

Read third `1`.

Now compare with `nums[write - 2]`:

```python
nums[0] = 1
num = 1
```

They are equal, so skip this number.

Read `2`.

Compare:

```python
nums[0] = 1
num = 2
```

They are different, so keep `2`:

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

Read second `2`.

Compare:

```python
nums[1] = 1
num = 2
```

They are different, so keep it:

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

Read `3`.

Compare:

```python
nums[2] = 2
num = 3
```

They are different, so keep it:

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

Return:

```python
5
```

The valid prefix is:

```python
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:

```python
n = len(nums)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each element is read once |
| Space | `O(1)` | Only a write index is used |

## Implementation

```python
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:

```python
write = 0
```

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

Then we scan the array:

```python
for num in nums:
```

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

```python
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:

```python
nums[write] = num
```

Then move the write pointer:

```python
write += 1
```

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

```python
return write
```

## Testing

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

```python
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:

| Test | Why |
|---|---|
| `[1, 1, 1, 2, 2, 3]` | Main example |
| Long mixed duplicate array | Checks several duplicate groups |
| `[1]` | Single element |
| `[1, 1]` | Exactly two copies allowed |
| `[1, 1, 1]` | Third copy removed |
| `[1, 2, 3]` | No duplicates |
| `[]` | Defensive local test, although LeetCode constraints may use non-empty arrays |