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:

nums = [3, 1, 2, 4]

A valid answer is:

[2, 4, 3, 1]

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

Input and Output

Function shape:

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

Examples

Example 1:

nums = [3, 1, 2, 4]

The even numbers are:

[2, 4]

The odd numbers are:

[3, 1]

One valid output is:

[2, 4, 3, 1]

Example 2:

nums = [0]

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

Answer:

[0]

First Thought: Build Two Lists

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

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:

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

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

Implementation

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:

left = 0
right = len(nums) - 1

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

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

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

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

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

They should be exchanged:

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.

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: