# LeetCode 283: Move Zeroes

## Problem Restatement

We are given an integer array `nums`.

We need to move all zeroes to the end of the array while keeping the relative order of all non-zero elements unchanged.

The operation must be done in-place.

For example:

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

should become:

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

The order of:

```python
1, 3, 12
```

must stay the same.

The official statement requires an in-place solution and encourages minimizing the total number of operations. ([leetcode.com](https://leetcode.com/problems/move-zeroes/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Nothing |
| Mutation | Modify `nums` in-place |
| Requirement | Preserve relative order of non-zero values |

Function shape:

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

## Examples

For:

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

The result should be:

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

For:

```python
nums = [0]
```

The result stays:

```python
[0]
```

For:

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

There are no zeroes, so the array remains:

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

## First Thought: Build Another Array

A direct solution is:

1. Collect all non-zero values.
2. Count how many zeroes exist.
3. Append that many zeroes at the end.
4. Copy everything back.

Example:

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

Non-zero values:

```python
[1, 3, 12]
```

Zero count:

```python
2
```

Final array:

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

Code:

```python
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        values = []

        for num in nums:
            if num != 0:
                values.append(num)

        zeroes = len(nums) - len(values)

        values.extend([0] * zeroes)

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

This works, but it uses extra memory.

The problem asks for an in-place solution.

## Key Insight

We only need to track where the next non-zero value should go.

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Current scanning position |
| `write` | Position where the next non-zero value should be written |

As we scan left to right:

- If `nums[i]` is non-zero, place it at `nums[write]`.
- Then advance `write`.

After all non-zero values are moved forward, every remaining position becomes zero.

## Algorithm

Initialize:

```python
write = 0
```

First pass:

Scan the array from left to right.

Whenever we see a non-zero value:

```python
nums[i] != 0
```

write it into:

```python
nums[write]
```

Then increment `write`.

After this pass, all non-zero values appear at the front in the correct order.

Second pass:

Fill the remaining positions with zeroes.

```python
while write < len(nums):
    nums[write] = 0
    write += 1
```

## Correctness

During the first pass, `write` always points to the first position where the next non-zero value should be placed.

Whenever the algorithm sees a non-zero value, it copies that value into `nums[write]` and increments `write`.

Because the scan proceeds from left to right, non-zero values are written in exactly the same order they originally appeared. Therefore relative order is preserved.

After the first pass:

- Positions before `write` contain all non-zero values in correct order.
- Positions from `write` onward are irrelevant temporary values.

The second pass fills every remaining position with zero.

So after completion:

1. All non-zero values appear first.
2. Their original order is preserved.
3. All remaining positions contain zero.

Therefore the final array satisfies the problem requirements.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array at most twice |
| Space | `O(1)` | No extra array proportional to input size |

## Implementation

```python
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        write = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                nums[write] = nums[i]
                write += 1

        while write < len(nums):
            nums[write] = 0
            write += 1
```

## Code Explanation

We start with:

```python
write = 0
```

This is where the next non-zero value should go.

Then we scan every element:

```python
for i in range(len(nums)):
```

If the current value is non-zero:

```python
if nums[i] != 0:
```

we move it forward:

```python
nums[write] = nums[i]
```

and advance the write position:

```python
write += 1
```

After the loop, all non-zero values are packed at the front.

The remaining positions should become zero:

```python
while write < len(nums):
    nums[write] = 0
    write += 1
```

The function returns nothing because the array is modified in-place.

## Alternative Swap Version

Another common implementation swaps elements immediately.

```python
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        write = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                nums[write], nums[i] = nums[i], nums[write]
                write += 1
```

This version may perform fewer writes in some cases.

Example:

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

Process:

```python
swap 1 with 0
swap 3 with 0
swap 12 with 0
```

Result:

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

## Testing

```python
def test_move_zeroes():
    s = Solution()

    nums = [0, 1, 0, 3, 12]
    s.moveZeroes(nums)
    assert nums == [1, 3, 12, 0, 0]

    nums = [0]
    s.moveZeroes(nums)
    assert nums == [0]

    nums = [1, 2, 3]
    s.moveZeroes(nums)
    assert nums == [1, 2, 3]

    nums = [0, 0, 0]
    s.moveZeroes(nums)
    assert nums == [0, 0, 0]

    nums = [4, 0, 5, 0, 0, 3]
    s.moveZeroes(nums)
    assert nums == [4, 5, 3, 0, 0, 0]

    print("all tests passed")

test_move_zeroes()
```

Test meaning:

| Test | Why |
|---|---|
| `[0, 1, 0, 3, 12]` | Standard example |
| `[0]` | Single zero |
| `[1, 2, 3]` | No zeroes |
| `[0, 0, 0]` | All zeroes |
| `[4, 0, 5, 0, 0, 3]` | Mixed positions and multiple zeroes |