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 <= 40nums.length is even.Half the elements are even and half are odd.0 <= nums[i] <= 1000
Hints for Sort Array By Parity II
Hint 1
Collect the evens and the odds into two lists, each keeping its original order.
Hint 2
Then interleave: the k-th even goes to index
2kand the k-th odd to index2k + 1.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
- Filter evens and odds (order preserved).
- 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 outJava
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