# LeetCode 905: Sort Array By Parity

## Problem Restatement

We are given an integer array `nums`.

We need to move all even integers to the beginning of the array and all odd integers after them.

The relative order does not matter.

Return any valid array.

For example:

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

A valid answer is:

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

Other answers such as `[4, 2, 1, 3]` are also valid.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | The same values rearranged |
| Rule | All even numbers must appear before all odd numbers |
| Order | Relative order does not matter |

Function shape:

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

## Examples

Example 1:

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

The even numbers are:

```python
[2, 4]
```

The odd numbers are:

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

One valid output is:

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

Example 2:

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

`0` is even, so the array already satisfies the condition.

Answer:

```python
[0]
```

## First Thought: Build Two Lists

A simple approach is to collect even numbers and odd numbers separately.

```python
class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        evens = []
        odds = []

        for num in nums:
            if num % 2 == 0:
                evens.append(num)
            else:
                odds.append(num)

        return evens + odds
```

This is easy to understand.

It runs in linear time, but it uses extra space for the two lists.

## Key Insight

We only need to partition the array into two regions:

```python
[ evens | odds ]
```

The order inside each region does not matter.

So we can use two pointers:

- `left` starts at the beginning.
- `right` starts at the end.

The left side should contain even numbers.

The right side should contain odd numbers.

If `nums[left]` is already even, it is in the correct side.

If `nums[right]` is already odd, it is in the correct side.

If `nums[left]` is odd and `nums[right]` is even, they are both misplaced, so we swap them.

## Algorithm

Set:

```python
left = 0
right = len(nums) - 1
```

While `left < right`:

1. If `nums[left]` is even, move `left` rightward.
2. Else if `nums[right]` is odd, move `right` leftward.
3. Otherwise, `nums[left]` is odd and `nums[right]` is even, so swap them.
4. Move both pointers after the swap.

Return `nums`.

## Correctness

The algorithm maintains two settled regions.

All elements before `left` are even.

All elements after `right` are odd.

At each step, one of three things happens.

If `nums[left]` is even, it belongs in the left region, so moving `left` preserves the invariant.

If `nums[right]` is odd, it belongs in the right region, so moving `right` preserves the invariant.

Otherwise, the left element is odd and the right element is even. Swapping them puts both elements into their correct sides. Moving both pointers then preserves the settled regions.

The loop stops when the pointers meet or cross. At that point, every element has been placed into the correct parity region.

Therefore, the returned array has all even numbers before all odd numbers.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each pointer moves across the array at most once |
| Space | `O(1)` | The rearrangement is done in place |

## Implementation

```python
class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        left = 0
        right = len(nums) - 1

        while left < right:
            if nums[left] % 2 == 0:
                left += 1
            elif nums[right] % 2 == 1:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        return nums
```

## Code Explanation

The two pointers start at opposite ends:

```python
left = 0
right = len(nums) - 1
```

If the left value is even, it is already on the correct side:

```python
if nums[left] % 2 == 0:
    left += 1
```

If the right value is odd, it is already on the correct side:

```python
elif nums[right] % 2 == 1:
    right -= 1
```

Otherwise, the left value is odd and the right value is even.

They should be exchanged:

```python
else:
    nums[left], nums[right] = nums[right], nums[left]
```

After swapping, both positions are correct, so both pointers move inward.

## Testing

Because the problem accepts many valid outputs, tests should check the property, not one exact array.

```python
def is_valid(nums):
    seen_odd = False

    for num in nums:
        if num % 2 == 1:
            seen_odd = True
        elif seen_odd:
            return False

    return True

def run_tests():
    s = Solution()

    result = s.sortArrayByParity([3, 1, 2, 4])
    assert sorted(result) == sorted([3, 1, 2, 4])
    assert is_valid(result)

    result = s.sortArrayByParity([0])
    assert result == [0]

    result = s.sortArrayByParity([2, 4, 6])
    assert sorted(result) == sorted([2, 4, 6])
    assert is_valid(result)

    result = s.sortArrayByParity([1, 3, 5])
    assert sorted(result) == sorted([1, 3, 5])
    assert is_valid(result)

    result = s.sortArrayByParity([1, 2, 3, 4, 5, 6])
    assert sorted(result) == sorted([1, 2, 3, 4, 5, 6])
    assert is_valid(result)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Mixed array | Checks normal partitioning |
| Single element | Minimum input |
| All even | Already valid |
| All odd | Already valid |
| Alternating parity | Requires several pointer moves |