Code Implementation

class Solution:
    def sortArrayByParity(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] % 2 > nums[right] % 2:
                nums[left], nums[right] = nums[right], nums[left]
            if nums[left] % 2 == 0:
                left += 1
            if nums[right] % 2 == 1:
                right -= 1
        return nums
      

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

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 > nums[right] % 2) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
            if (nums[left] % 2 == 0) left++;
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }
}
      

var sortArrayByParity = function(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        if (nums[left] % 2 > nums[right] % 2) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
        }
        if (nums[left] % 2 === 0) left++;
        if (nums[right] % 2 === 1) right--;
    }
    return nums;
};
      

Problem Description

You are given an array of non-negative integers called nums. The task is to reorder the array so that all even integers appear before all odd integers. The function should return the reordered array. You do not need to maintain the relative order of the even or odd numbers.

• Each element in nums must appear exactly once in the result (do not reuse or omit elements).
• There can be multiple valid solutions, as long as all even numbers come before all odd numbers.

For example, given nums = [3,1,2,4], one valid output is [2,4,3,1] (evens first, then odds).

Thought Process

The core challenge is to efficiently separate even and odd numbers in the array, ensuring all evens are at the front and all odds at the back. A brute-force idea would be to create two new arrays: one for evens and one for odds, then concatenate them. However, this uses extra space and is not as efficient as possible.

To optimize, we can try sorting the array "in place" using two pointers: one starting from the left and one from the right. By swapping elements when needed, we can ensure all evens end up on the left and all odds on the right, without using extra space.

This approach is similar to partitioning in quicksort, where we separate elements based on a condition (here: evenness).

Solution Approach

We will use a two-pointer technique to sort the array by parity in place:

1. Initialize two pointers: left at the start (index 0) and right at the end (last index) of the array.
2. While left < right, do the following:
   • If nums[left] is odd and nums[right] is even, swap them. This moves the even number to the left and the odd number to the right.
   • If nums[left] is even, increment left (it's already in the correct place).
   • If nums[right] is odd, decrement right (it's already in the correct place).
3. Continue this process until the two pointers meet or cross.
4. Return the modified array, which now has all even numbers before all odd numbers.

This method works efficiently in-place and does not require any extra arrays.

Example Walkthrough

Let's walk through an example with nums = [3, 1, 2, 4]:

1. Initial state: [3, 1, 2, 4], left = 0, right = 3
2. nums[left] = 3 (odd), nums[right] = 4 (even).
   • Since left is odd and right is even, swap.
   • Array becomes [4, 1, 2, 3].
3. Now, nums[left] = 4 (even), so increment left to 1.
4. nums[right] = 3 (odd), so decrement right to 2.
5. nums[left] = 1 (odd), nums[right] = 2 (even).
   • Swap again. Array becomes [4, 2, 1, 3].
6. nums[left] = 2 (even), increment left to 2.
7. nums[right] = 1 (odd), decrement right to 1.
8. Now left >= right, so we stop. The result is [4, 2, 1, 3], with evens first.

Time and Space Complexity

• Brute-force Approach: If we used two extra arrays (for evens and odds), we'd have O(n) time and O(n) space complexity, since we must iterate through the array and allocate new arrays.
• Optimized Two-Pointer Approach: The in-place two-pointer method has O(n) time complexity, as each element is checked at most once. The space complexity is O(1), since no additional arrays proportional to input size are used.

This makes the two-pointer solution both fast and memory efficient.

Summary

By leveraging the two-pointer technique, we can efficiently partition the array into evens and odds in a single pass, without extra memory. This approach is both intuitive and optimal for the problem, making it an elegant solution for sorting an array by parity.