Sort Array By Parity

How it works

This approach uses a slow and fast pointer moving in the same direction. The slow pointer l tracks where the next even number should be placed. The fast pointer r scans through the array. Whenever we find an even number, we swap it to position l and advance l. This collects all even numbers at the front.

Steps

1. Initialize a slow pointer l at 0.
2. Iterate through the array with a fast pointer r:
   • If nums[r] is even, swap nums[l] with nums[r] and increment l.
3. Return the modified array.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Incrementing the Pointer After Swapping with the Right Boundary

In the two-pointer approach where you swap odd elements to the right, you must not increment the left pointer after a swap. The element swapped from the right side has not been checked yet and could be odd, requiring another swap.

Using Modulo on Negative Numbers

While this problem only has non-negative integers, using num % 2 can behave unexpectedly with negative numbers in some languages (returning -1 instead of 1 for odd negatives). Using bitwise AND (num & 1) is safer and more efficient for parity checking.

from typing import List

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        l = 0
        for r in range(len(nums)):
            if nums[r] % 2 == 0:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
        return nums

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        for (int l = 0, r = 0; r < nums.size(); r++) {
            if (nums[r] % 2 == 0) {
                swap(nums[l], nums[r]);
                l++;
            }
        }
        return nums;
    }
};