# LeetCode 26: Remove Duplicates from Sorted Array

## Problem Restatement

We are given an integer array `nums`.

The array is already sorted in non-decreasing order.

We need to remove duplicate values in place so that every unique value appears only once. The relative order of the values must stay the same.

After modifying the array, return `k`, the number of unique values.

Only the first `k` elements matter. Values after index `k - 1` can be ignored.

The official custom judge checks that `k` is correct and that `nums[0:k]` contains the expected unique values in order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | An integer `k` |
| Required mutation | The first `k` elements of `nums` must contain the unique values |
| Extra space | Must modify `nums` in place |

Function shape:

```python
def removeDuplicates(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

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

The unique values are:

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

So we modify the beginning of `nums`:

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

Return:

```python
2
```

Example 2:

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

The unique values are:

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

So the first five positions should become:

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

Return:

```python
5
```

## First Thought: Brute Force

One simple idea is to build a new array of unique values.

Since the array is sorted, we can scan from left to right and append a value only when it differs from the previous value.

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

        for num in nums:
            if len(unique) == 0 or unique[-1] != num:
                unique.append(num)

        for i in range(len(unique)):
            nums[i] = unique[i]

        return len(unique)
```

This gives the right first `k` elements.

But it uses an extra array, so it does not follow the in-place requirement.

## Problem With Brute Force

The problem asks us to modify `nums` directly.

Using another array makes the logic easy, but it spends extra memory proportional to the number of unique values.

We need to keep the same idea, but write the unique values back into `nums` while scanning.

## Key Insight

Because `nums` is sorted, equal values are adjacent.

So we only need to compare the current value with the last unique value we have written.

Use two positions:

| Name | Meaning |
|---|---|
| `read` | Scans every element in the original array |
| `write` | Points to the next position where a unique value should be written |

The section before `write` always contains the unique values found so far.

## Algorithm

Start with:

```python
write = 1
```

The first element is always unique because there is nothing before it.

Then scan from index `1` to the end.

For each index `read`:

```python
if nums[read] != nums[write - 1]:
    nums[write] = nums[read]
    write += 1
```

The comparison checks whether the current value differs from the last unique value.

If it differs, we copy it to the next write position.

At the end, `write` is the number of unique values.

## Correctness

At every step, the subarray `nums[0:write]` contains all unique values seen so far, in the same order as the original array.

When `nums[read]` equals `nums[write - 1]`, it is a duplicate of the last unique value. Since the array is sorted, this duplicate belongs to the current run of equal values, so skipping it is correct.

When `nums[read]` differs from `nums[write - 1]`, it is the first occurrence of a new value. Writing it to `nums[write]` appends exactly one copy of this new value to the unique prefix.

After the scan finishes, every unique value has been written once, and every duplicate has been skipped. Therefore, the first `write` elements of `nums` contain the required answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We only use two integer variables |

## Implementation

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

        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write
```

## Code Explanation

The variable `write` stores the length of the unique prefix.

```python
write = 1
```

This is valid because the constraints say `nums.length >= 1`.

The loop starts at index `1` because index `0` is already part of the unique prefix.

```python
for read in range(1, len(nums)):
```

When the current value differs from the last written unique value, we found a new unique value.

```python
if nums[read] != nums[write - 1]:
```

We copy it into the next available position.

```python
nums[write] = nums[read]
```

Then we grow the unique prefix.

```python
write += 1
```

Finally, return the number of unique values.

```python
return write
```

## Testing

```python
def check(nums: list[int], expected: list[int]) -> None:
    original = nums[:]
    k = Solution().removeDuplicates(nums)

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 1, 2]` | Basic duplicate case |
| `[0,0,1,1,1,2,2,3,3,4]` | Multiple duplicate groups |
| `[1]` | Minimum valid input |
| `[1,2,3]` | Already unique |
| Negative numbers | Confirms the logic does not depend on positive values |