Sort Array By Parity II

Easy
353.

Sort Array By Parity II

Sort Array By Parity II is an easy coding problem on arrays, sorting and two pointers, asked in Amazon and Meta interviews.

Given an array nums of non-negative integers, half of which are even and half odd, rearrange it so that nums[i] is even whenever i is even and odd whenever i is odd.

Within each parity class, keep the elements in their original relative order.

Example 1

Input
nums = [4,2,5,7]
Output
[4,5,2,7]

Example 2

Input
nums = [2,3]
Output
[2,3]

Example 3

Input
nums = [3,4]
Output
[4,3]

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • Half the elements are even and half are odd.
  • 0 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParityII = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort Array By Parity II — Solution in Python, Java & C++

Sort Array By Parity II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sort Array By Parity II is an easy coding problem on arrays, sorting and two pointers, asked in Amazon and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums of non-negative integers, half of which are even and half odd, rearrange it so that nums[i] is even whenever i is even and odd whenever i is odd.

Within each parity class, keep the elements in their original relative order.

Example 1

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

Example 2

Input: nums = [2,3]
Output: [2,3]

Example 3

Input: nums = [3,4]
Output: [4,3]

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • Half the elements are even and half are odd.
  • 0 <= nums[i] <= 1000

Hints for Sort Array By Parity II

  1. Hint 1

    Collect the evens and the odds into two lists, each keeping its original order.

  2. Hint 2

    Then interleave: the k-th even goes to index 2k and the k-th odd to index 2k + 1.

  3. Hint 3

    The classic in-place version walks two pointers over the even and odd slots and swaps mismatches — but that does not preserve order.

How to solve Sort Array By Parity II

Split evens and odds in original order, then interleave: k-th even at 2k, k-th odd at 2k + 1.

Approach

  1. Filter evens and odds (order preserved).
  2. Zip them into the output alternately.

Why it works

The halves are equal in size, so the zip fills every index, and filtering preserves the required relative order within each parity class.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The in-place swap version is O(1) space but does not preserve order, which this variant requires.

Reference solution

Python

def sortArrayByParityII(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    out = []
    for e, o in zip(evens, odds):
        out.append(e)
        out.append(o)
    return out

Java

public static int[] sortArrayByParityII(int[] nums) {
    int[] out = new int[nums.length];
    int e = 0, o = 1;
    for (int x : nums) {
        if (x % 2 == 0) {
            out[e] = x;
            e += 2;
        } else {
            out[o] = x;
            o += 2;
        }
    }
    return out;
}

C++

vector<int> sortArrayByParityII(vector<int>& nums) {
    vector<int> out(nums.size(), 0);
    int e = 0, o = 1;
    for (int x : nums) {
        if (x % 2 == 0) {
            out[e] = x;
            e += 2;
        } else {
            out[o] = x;
            o += 2;
        }
    }
    return out;
}

JavaScript

var sortArrayByParityII = function(nums) {
    const evens = [], odds = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 0) evens.push(nums[i]);
        else odds.push(nums[i]);
    }
    const out = [];
    for (let i = 0; i < evens.length; i++) {
        out.push(evens[i]);
        out.push(odds[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms