Sort Array By Parity — Solution in Python, Java & C++
Sort Array By Parity solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sort Array By Parity is an easy coding problem on arrays, sorting and two pointers, asked in Amazon, Adobe and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Two Pointers
- Asked at: Amazon, Adobe, 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 integer array nums, move every even element in front of every odd element.
Within each group, keep the elements in their original relative order (a stable partition).
Example 1
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The evens 2 and 4 keep their order, then the odds 3 and 1 keep theirs.
Example 2
Input: nums = [0]
Output: [0]
Example 3
Input: nums = [1,3,5]
Output: [1,3,5]
Explanation: No evens, so nothing moves.
Constraints
1 <= nums.length <= 400 <= nums[i] <= 1000
Hints for Sort Array By Parity
Hint 1
Collect the evens in one pass and the odds in another, then concatenate.
Hint 2
A single pass appending into two lists works just as well.
Hint 3
The stability requirement rules out the classic two-pointer swap, which reorders within each group.
How to solve Sort Array By Parity
Collect evens and odds in separate lists, preserving order within each, then concatenate.
Approach
- Filter the evens in order.
- Filter the odds in order.
- Return
evens + odds.
Why it works
Filtering preserves relative order, which is what makes the partition stable.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The in-place two-pointer swap reorders elements within each group and fails the stability requirement here.
Reference solution
Python
def sortArrayByParity(nums):
evens = [x for x in nums if x % 2 == 0]
odds = [x for x in nums if x % 2 != 0]
return evens + oddsJava
public static int[] sortArrayByParity(int[] nums) {
int[] out = new int[nums.length];
int pos = 0;
for (int x : nums) {
if (x % 2 == 0) out[pos++] = x;
}
for (int x : nums) {
if (x % 2 != 0) out[pos++] = x;
}
return out;
}C++
vector<int> sortArrayByParity(vector<int>& nums) {
vector<int> out;
for (int x : nums) {
if (x % 2 == 0) out.push_back(x);
}
for (int x : nums) {
if (x % 2 != 0) out.push_back(x);
}
return out;
}JavaScript
var sortArrayByParity = 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]);
}
return evens.concat(odds);
};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