Sort Array By Parity

Problem Statement

Given an array nums, move every even number before every odd number. Any valid arrangement is accepted.

Example

Input:  nums = [3,1,2,4]
Output: [2,4,3,1]  (or any arrangement with evens first)

Two Pointer Approach

Use two pointers from both ends. If left is already even, advance it. If right is already odd, move it back. When left is odd and right is even, swap them.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def sortArrayByParity(nums):
    left, right = 0, 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

Java

int[] sortArrayByParity(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        if (nums[left] % 2 == 0) left++;
        else if (nums[right] % 2 == 1) right--;
        else {
            int t = nums[left]; nums[left] = nums[right]; nums[right] = t;
            left++; right--;
        }
    }
    return nums;
}

C++

vector<int> sortArrayByParity(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        if (nums[left] % 2 == 0) left++;
        else if (nums[right] % 2 == 1) right--;
        else { swap(nums[left], nums[right]); left++; right--; }
    }
    return nums;
}

Key Takeaways

• This is an in-place partition driven by a simple parity predicate.
• The same two pointer partition underlies quicksort's Lomuto/Hoare schemes.
• Only swap when both sides are out of place.