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:

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

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:

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:

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

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: