Sort Array By Parity II

easy array two pointers parity

Problem

Given an array of integers nums where half the integers are even and half are odd, rearrange it so that whenever nums[i] is even, i is even, and whenever nums[i] is odd, i is odd. Return any answer array that satisfies this condition.

Inputnums = [4, 2, 5, 7]

Output[4, 5, 2, 7]

Even values 4, 2 land on even indices 0, 2; odd values 5, 7 land on odd indices 1, 3. Other valid answers exist.

nums (comma-separated, equal evens & odds)

def sort_array_by_parity_ii(nums):
    even, odd = 0, 1
    n = len(nums)
    while even < n:
        if nums[even] % 2 == 0:
            even += 2
        elif nums[odd] % 2 == 1:
            odd += 2
        else:
            nums[even], nums[odd] = nums[odd], nums[even]
    return nums

function sortArrayByParityII(nums) {
  let even = 0, odd = 1;
  const n = nums.length;
  while (even < n) {
    if (nums[even] % 2 === 0) {
      even += 2;
    } else if (nums[odd] % 2 === 1) {
      odd += 2;
    } else {
      [nums[even], nums[odd]] = [nums[odd], nums[even]];
    }
  }
  return nums;
}

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int even = 0, odd = 1, n = nums.length;
        while (even < n) {
            if (nums[even] % 2 == 0) {
                even += 2;
            } else if (nums[odd] % 2 == 1) {
                odd += 2;
            } else {
                int t = nums[even];
                nums[even] = nums[odd];
                nums[odd] = t;
            }
        }
        return nums;
    }
}

vector<int> sortArrayByParityII(vector<int>& nums) {
    int even = 0, odd = 1, n = (int)nums.size();
    while (even < n) {
        if (nums[even] % 2 == 0) {
            even += 2;
        } else if (nums[odd] % 2 == 1) {
            odd += 2;
        } else {
            swap(nums[even], nums[odd]);
        }
    }
    return nums;
}

Explanation

We want even values at even indices and odd values at odd indices. The neat in-place trick is to keep two separate pointers: even walking the even indices (0, 2, 4, ...) and odd walking the odd indices (1, 3, 5, ...).

We advance even while the value sitting there is already even — it is in the right kind of slot. Likewise we advance odd while its value is already odd.

The interesting case is when even is stuck on an odd value. That odd value belongs at an odd index, and somewhere the odd pointer is stuck on an even value that belongs at an even index. So we swap them and both are fixed at once.

Each swap places two numbers correctly, and the pointers only move forward, so the whole thing is one linear pass using O(1) extra space.

Example: nums = [4, 2, 5, 7]. even sees 4 (even, ok) and 5 at index 2 (odd, stuck); odd sees 2 at index 1 (even, stuck). Swap indices 2 and 1 → [4, 5, 2, 7], which satisfies the condition.

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