LeetCode 905 - Sort Array By Parity

LeetCode Problem 905

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

The problem asks us to rearrange an array so that all even numbers appear before all odd numbers. The relative ordering among even numbers does not matter, and the relative ordering among odd numbers also does not matter. The problem explicitly states that any valid arrangement is acceptable.

We are given an integer array nums. Each element is a non negative integer. Our goal is to return the same array, or another array, where every even value comes first and every odd value comes afterward.

For example, if the input is:

[3,1,2,4]

then valid outputs include:

[2,4,3,1]
[4,2,1,3]
[2,4,1,3]

because all even numbers are grouped at the beginning and all odd numbers are grouped at the end.

The constraints are relatively small:

• The array length is between 1 and 5000
• Each number is between 0 and 5000

These limits tell us that even an O(n log n) sorting solution would work comfortably. However, the problem can actually be solved in linear time using a two pointer technique.

An important observation is that parity is determined by checking whether a number is divisible by 2:

• Even number: num % 2 == 0
• Odd number: num % 2 == 1

Several edge cases are worth considering:

• Arrays containing only even numbers
• Arrays containing only odd numbers
• Arrays with a single element
• Arrays where even and odd numbers alternate frequently
• Arrays containing zero, since 0 is even

The problem guarantees that the input array is non empty, so we never need to handle a completely empty input.

Approaches

Brute Force Approach

A straightforward solution is to create two separate lists:

1. One list for even numbers
2. One list for odd numbers

We iterate through the array once. For each value:

• If it is even, append it to the even list
• Otherwise, append it to the odd list

At the end, concatenate the two lists and return the result.

This works because every even number is guaranteed to appear before every odd number in the final concatenated array.

Although this approach is already efficient enough for the constraints, it uses additional memory proportional to the size of the input.

Optimal Approach, Two Pointers

The key insight is that we do not actually need extra arrays. We can rearrange the elements in place.

We maintain two pointers:

• A left pointer that searches for misplaced odd numbers
• A right pointer that searches for misplaced even numbers

If the left pointer finds an odd number and the right pointer finds an even number, we swap them. This gradually pushes even numbers toward the front and odd numbers toward the back.

This approach works well because the problem does not require preserving the original order of elements. Since any valid arrangement is accepted, swapping is completely safe.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses separate lists for evens and odds
Optimal	O(n)	O(1)	Uses in place two pointer swapping

Algorithm Walkthrough

Optimal Two Pointer Algorithm

1. Initialize two pointers:

• left = 0
• right = len(nums) - 1

The left pointer scans from the beginning, while the right pointer scans from the end. 2. Continue processing while left < right.

This ensures the pointers have not crossed. 3. Check whether the value at left is already even.

If it is even, it is already in the correct region of the array, so increment left. 4. Check whether the value at right is already odd.

If it is odd, it already belongs near the end, so decrement right. 5. If the left side contains an odd number and the right side contains an even number, swap them.

After the swap:

• The even number moves toward the front
• The odd number moves toward the back

6. Move both pointers inward after swapping.

This avoids reprocessing elements that are now correctly positioned. 7. When the pointers cross, every even number will be before every odd number.

Why it works

The algorithm maintains an invariant during execution:

• All elements before left are even
• All elements after right are odd

Whenever we find a misplaced odd number on the left and a misplaced even number on the right, swapping fixes both positions simultaneously. Since the pointers continuously move inward, every element is processed at most once, and the array eventually becomes partitioned into evens followed by odds.

Python Solution

from typing import List

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

The implementation starts by creating two pointers at opposite ends of the array.

Inside the loop, the algorithm first checks whether the left value is already even. If so, the left pointer advances because that element is correctly placed.

Next, it checks whether the right value is already odd. If so, the right pointer moves backward because that element is also correctly placed.

If neither condition is true, then:

• The left side contains an odd number
• The right side contains an even number

These elements are misplaced relative to the desired partition, so the algorithm swaps them.

After the swap, both pointers move inward because both newly placed elements are now correct.

Finally, the modified array is returned.

Go Solution

func sortArrayByParity(nums []int) []int {
    left := 0
    right := len(nums) - 1

    for left < right {
        if nums[left]%2 == 0 {
            left++
        } else if nums[right]%2 == 1 {
            right--
        } else {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }

    return nums
}

The Go implementation follows the exact same logic as the Python version. Since slices in Go behave similarly to references to arrays, modifications happen in place automatically.

Go does not require special handling for integer overflow here because all values are very small. The algorithm also works correctly for slices of length 1 because the loop condition left < right immediately fails.

Worked Examples

Example 1

Input:

nums = [3,1,2,4]

Initial state:

Left	Right	Array
0	3	[3,1,2,4]

Step 1:

• nums[left] = 3, odd
• nums[right] = 4, even
• Swap them

Left	Right	Array
1	2	[4,1,2,3]

Step 2:

• nums[left] = 1, odd
• nums[right] = 2, even
• Swap them

Left	Right	Array
2	1	[4,2,1,3]

Now left > right, so the algorithm stops.

Final result:

[4,2,1,3]

This is valid because all even numbers appear before all odd numbers.

Example 2

Input:

nums = [0]

Initial state:

Left	Right	Array
0	0	[0]

Since left < right is false immediately, the loop never runs.

Final result:

[0]

The array already satisfies the condition because 0 is even.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves across the array at most once
Space	O(1)	Rearrangement happens in place

The time complexity is linear because each element is processed at most once by either the left pointer or the right pointer. No nested iteration occurs.

The space complexity is constant because the algorithm only uses a few integer variables regardless of input size. No additional arrays or data structures are allocated.

Test Cases

def is_valid_parity_order(arr):
    found_odd = False

    for num in arr:
        if num % 2 == 1:
            found_odd = True
        elif found_odd:
            return False

    return True

sol = Solution()

# Provided example
result = sol.sortArrayByParity([3, 1, 2, 4])
assert is_valid_parity_order(result)  # mixed even and odd numbers

# Single even element
result = sol.sortArrayByParity([0])
assert result == [0]  # smallest possible input

# All even numbers
result = sol.sortArrayByParity([2, 4, 6, 8])
assert is_valid_parity_order(result)  # already valid

# All odd numbers
result = sol.sortArrayByParity([1, 3, 5, 7])
assert is_valid_parity_order(result)  # no swaps needed

# Alternating parity
result = sol.sortArrayByParity([1, 2, 3, 4, 5, 6])
assert is_valid_parity_order(result)  # frequent swapping

# Even numbers at the end
result = sol.sortArrayByParity([1, 3, 5, 2, 4, 6])
assert is_valid_parity_order(result)  # many misplaced elements

# Even numbers at the beginning
result = sol.sortArrayByParity([2, 4, 6, 1, 3, 5])
assert is_valid_parity_order(result)  # already partitioned

# Duplicate values
result = sol.sortArrayByParity([2, 2, 1, 1, 4, 4, 3, 3])
assert is_valid_parity_order(result)  # repeated numbers

# Large values within constraints
result = sol.sortArrayByParity([5000, 4999, 4000, 3999])
assert is_valid_parity_order(result)  # boundary numeric values

Test	Why
[3,1,2,4]	Standard mixed parity example
[0]	Smallest valid input
[2,4,6,8]	All elements already even
[1,3,5,7]	All elements odd
[1,2,3,4,5,6]	Alternating parity pattern
[1,3,5,2,4,6]	Many misplaced values
[2,4,6,1,3,5]	Already partitioned correctly
[2,2,1,1,4,4,3,3]	Duplicate values
[5000,4999,4000,3999]	Constraint boundary values

Edge Cases

Single Element Array

An array containing only one element can easily expose boundary condition bugs. For example, pointer based implementations may accidentally access invalid indices if loop conditions are incorrect.

This implementation handles the case safely because the loop only executes while left < right. For a single element array, both pointers start at index 0, so the loop never runs.

All Even or All Odd Arrays

Arrays where every element has the same parity can cause unnecessary swaps in poorly designed solutions.

For example:

[2,4,6,8]

or

[1,3,5,7]

In this implementation, the pointers simply move inward without performing swaps because every element is already correctly positioned relative to the partition.

Zero in the Input

Some implementations incorrectly treat zero as a special case. However, mathematically, zero is an even number because it is divisible by two.

This solution correctly classifies zero using:

num % 2 == 0

Therefore arrays such as:

[0,1,2]

are processed correctly, with zero placed among the even values at the front.