Sort Array By Parity

easy two pointers array partition

Problem

Given an integer array nums, move every even integer in front of every odd integer and return the result. Any arrangement that satisfies this condition is accepted, so the relative order within each group does not matter.

Inputnums = [3, 1, 2, 4]

Output[4, 2, 1, 3]

Evens (4, 2) come before odds (1, 3). [2, 4, 3, 1] would also be a valid answer.

nums (comma-separated)

def sort_array_by_parity(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

function sortArrayByParity(nums) {
  let left = 0, right = nums.length - 1;
  while (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;
}

class Solution {
    public 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 tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

vector<int> sortArrayByParity(vector<int>& nums) {
    int left = 0, right = (int)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;
}

Explanation

We just need all even numbers before all odd numbers; the order within each group does not matter. That freedom lets us use a simple in-place two-pointer partition with left at the front and right at the back.

If nums[left] is already even, it belongs on the left, so we move left forward. If nums[right] is already odd, it belongs on the right, so we move right backward.

When left points at an odd value and right points at an even value, both are on the wrong side. We swap them and step both pointers inward. This grows an even region from the left and an odd region from the right until they meet.

Every element is examined once, so it runs in linear time with O(1) extra memory.

Example: nums = [3, 1, 2, 4]. left sees 3 (odd), right sees 4 (even) — swap → [4, 1, 2, 3]. Now 4 is even (advance left), and the rest settles into evens-before-odds, e.g. [4, 2, 1, 3].

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