# LeetCode 922: Sort Array By Parity II

## Problem Restatement

We are given an integer array `nums`.

Exactly half of the numbers are even, and exactly half are odd.

We need to rearrange the array so that:

| Index | Required value |
|---:|---|
| Even index | Even number |
| Odd index | Odd number |

Return any valid arrangement.

For example:

```python
nums = [4, 2, 5, 7]
```

One valid answer is:

```python
[4, 5, 2, 7]
```

because indices `0` and `2` contain even numbers, and indices `1` and `3` contain odd numbers. The problem accepts any valid arrangement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Any rearranged valid array |
| Even index rule | `nums[i]` must be even when `i` is even |
| Odd index rule | `nums[i]` must be odd when `i` is odd |
| Guarantee | Half the numbers are even and half are odd |

Function shape:

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

## Examples

Example 1:

```python
nums = [4, 2, 5, 7]
```

Valid output:

```python
[4, 5, 2, 7]
```

Check each index:

| Index | Value | Valid |
|---:|---:|---|
| 0 | 4 | Even index, even value |
| 1 | 5 | Odd index, odd value |
| 2 | 2 | Even index, even value |
| 3 | 7 | Odd index, odd value |

Example 2:

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

Output:

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

The array already satisfies the rule.

## First Thought: Build Separate Lists

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

Then place even numbers at even indices and odd numbers at odd indices.

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

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

        result = [0] * len(nums)

        even_index = 0
        odd_index = 0

        for i in range(len(nums)):
            if i % 2 == 0:
                result[i] = evens[even_index]
                even_index += 1
            else:
                result[i] = odds[odd_index]
                odd_index += 1

        return result
```

This is clear and correct, but it uses extra arrays.

The follow-up asks whether we can solve it in place.

## Key Insight

Use two pointers:

| Pointer | Visits | Looks for |
|---|---|---|
| `even` | Even indices `0, 2, 4, ...` | An odd value in the wrong place |
| `odd` | Odd indices `1, 3, 5, ...` | An even value in the wrong place |

If an even index contains an odd number, then some odd index must contain an even number.

Why?

Because the array has exactly the same number of even values as even positions. If one even position is wrong, one odd position must also be wrong.

So we can swap those two misplaced values.

## Algorithm

1. Set `even = 0`.
2. Set `odd = 1`.
3. While both pointers are inside the array:
   - Move `even` forward by `2` while `nums[even]` is even.
   - Move `odd` forward by `2` while `nums[odd]` is odd.
   - If both pointers are still valid, swap `nums[even]` and `nums[odd]`.
4. Return `nums`.

## Correctness

The algorithm only swaps when both positions are wrong.

At an even index, an odd value is invalid.

At an odd index, an even value is invalid.

Swapping those two values fixes both positions at once.

The `even` pointer skips every even index that already contains an even value. The `odd` pointer skips every odd index that already contains an odd value. Therefore, once a pointer passes an index, that index is correct and will never need to change again.

Because the input has exactly half even numbers and half odd numbers, every misplaced odd value at an even index can be paired with a misplaced even value at an odd index.

The process ends after all even and odd positions have been checked.

Therefore, the returned array satisfies the required parity rule at every index.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each pointer moves across its index parity once |
| Space | `O(1)` | The array is rearranged in place |

## Implementation

```python
class Solution:
    def sortArrayByParityII(self, nums: list[int]) -> list[int]:
        n = len(nums)

        even = 0
        odd = 1

        while even < n and odd < n:
            while even < n and nums[even] % 2 == 0:
                even += 2

            while odd < n and nums[odd] % 2 == 1:
                odd += 2

            if even < n and odd < n:
                nums[even], nums[odd] = nums[odd], nums[even]

        return nums
```

## Code Explanation

The even pointer starts at the first even index:

```python
even = 0
```

The odd pointer starts at the first odd index:

```python
odd = 1
```

Skip correct even positions:

```python
while even < n and nums[even] % 2 == 0:
    even += 2
```

Skip correct odd positions:

```python
while odd < n and nums[odd] % 2 == 1:
    odd += 2
```

When both pointers stop, they point to two misplaced values:

```python
nums[even], nums[odd] = nums[odd], nums[even]
```

The swap fixes both positions.

Finally, return the modified array:

```python
return nums
```

## Testing

Because many valid outputs are accepted, tests should check the property rather than one exact order.

```python
def is_valid(nums):
    for i, num in enumerate(nums):
        if i % 2 != num % 2:
            return False
    return True

def run_tests():
    s = Solution()

    result = s.sortArrayByParityII([4, 2, 5, 7])
    assert sorted(result) == sorted([4, 2, 5, 7])
    assert is_valid(result)

    result = s.sortArrayByParityII([2, 3])
    assert sorted(result) == sorted([2, 3])
    assert is_valid(result)

    result = s.sortArrayByParityII([3, 2])
    assert sorted(result) == sorted([3, 2])
    assert is_valid(result)

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4, 2, 5, 7]` | Main sample |
| `[2, 3]` | Already valid minimum case |
| `[3, 2]` | Both positions need swapping |
| `[1, 4, 3, 2]` | Multiple misplaced values |
| Larger mixed array | Checks pointer movement across several positions |