3.30 Sort Array By Parity

3.30.1 Problem Metadata

3.30.2 Description

Given an array A of non-negative integers, return any array consisting of all the even elements of A followed by all the odd elements.

3.30.3 Examples

Input: [3,1,2,4]
Output: [2,4,3,1]

3.30.4 Constraints

  • 1 <= A.length <= 5000
  • 0 <= A[i] <= 5000

3.30.5 Solution - Two Pointers

3.30.5.1 Walkthrough

Use two pointers. Advance left until an odd number is found and decrement right until an even number is found; swap them and continue until the pointers cross.

3.30.5.2 Analysis

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

3.30.5.3 Implementation Steps

  1. Set left = 0, right = A.length - 1.
  2. While left < right:
    1. Increment left while A[left] is even.
    2. Decrement right while A[right] is odd.
    3. If left < right, swap A[left] and A[right].
  3. Return A.

3.30.5.4 Code - Java

public int[] sortArrayByParity(int[] A) {
    int left = 0;
    int right = A.length - 1;

    while (left < right) {
        while (left < right && (A[left] & 1) == 0) {
            left++;
        }
        while (left < right && (A[right] & 1) == 1) {
            right--;
        }
        if (left < right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
    }

    return A;
}