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:

nums = [4, 2, 5, 7]

One valid answer is:

[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:

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

Examples

Example 1:

nums = [4, 2, 5, 7]

Valid output:

[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:

nums = [2, 3]

Output:

[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.

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

Set even = 0.
Set odd = 1.
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].
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

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:

even = 0

The odd pointer starts at the first odd index:

odd = 1

Skip correct even positions:

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

Skip correct odd positions:

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

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

nums[even], nums[odd] = nums[odd], nums[even]

The swap fixes both positions.

Finally, return the modified array:

return nums

Testing

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

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