Community Problem
Sort Array By Parity
Difficulty: Easy
Rearrange the array so that every even integer appears before every odd integer; any valid arrangement is accepted.
Sort Array By Parity
Rearrange the array so that every even integer appears before every odd integer; any valid arrangement is accepted.
By @riverbanda
December 20, 2025
·
Updated May 18, 2026
180 views
2
4.0 (9)
I keep coming back to this one whenever a candidate tells me they are comfortable with two pointers but only ever practice on Two Sum. The trick is the partition shape: there is no relative-order requirement, just a "all evens left of all odds" invariant, which makes the in-place swap version a clean stress test for whether the two-pointer mental model has actually clicked.
Sort Array By Parity
Given an integer array nums, move every even integer to the front and every odd integer to the back. Return any array that satisfies this property. The relative order among the even values does not need to be preserved, and the relative order among the odd values does not need to be preserved either.
Examples
Example 1:
- Input:
nums = [3, 1, 2, 4] - Output:
[2, 4, 3, 1] - Explanation:
[2, 4, 1, 3],[4, 2, 1, 3], and[4, 2, 3, 1]are also accepted; any output with both evens at the front is valid.
Example 2:
- Input:
nums = [0] - Output:
[0] - Explanation: A single element is trivially sorted by parity.
Example 3:
- Input:
nums = [1, 3, 5] - Output:
[1, 3, 5] - Explanation: All odd, no rearrangement is required.
Example 4:
- Input:
nums = [2, 4, 6] - Output:
[2, 4, 6] - Explanation: All even, no rearrangement is required.
Constraints
1 <= nums.length <= 50000 <= nums[i] <= 5000
Follow-up
Can you solve this in O(n) time and O(1) extra space, without a second array? The expected solution uses two pointers walking from opposite ends and swaps misplaced pairs.
Solution
Hints
Solution Walkthrough
Approach: Two Pointers, Swap Misplaced Pairs (O(n) time, O(1) extra space)
The weakest acceptable algorithm is a one-pass scan into a fresh array (push evens, push odds, concatenate), but that costs O(n) extra space and misses the actual lesson. The interview-grade answer is a partition with two pointers: walk left from the front while it sees evens, walk right from the back while it sees odds, and when both are stuck on misplaced values, swap them and step both inward.
Algorithm
- Initialize
left = 0andright = n - 1. - While
left < right:- If
nums[left]is even, advanceleftby one (it is already in the correct partition). - Else if
nums[right]is odd, decrementrightby one (already in the correct partition). - Else swap
nums[left]andnums[right], then advanceleftand decrementright.
- Return
nums.
Why It Works
The loop invariant is: every index strictly less than left is even, and every index strictly greater than right is odd. The only way to violate the invariant is for left to point at an odd value AND right to point at an even value at the same time, in which case the swap fixes both, and the increment/decrement extends the invariant by one position on each side. When left >= right, the invariant covers the entire array, so the partition is complete.
Complexity
Metric Value
Time O(n), each element is visited at most once across both pointers
Space O(1) extra, the partition is in placePitfalls
- Forgetting
continue. If you fall through after advancing only one pointer, you can swap a value that is already in the correct partition and corrupt the invariant. - Treating zero as odd.
0 % 2 === 0in both languages, so zero belongs to the even partition. Some candidates accidentally writenums[i] & 1 === 0, which still works for non-negative integers but is one parsing-precedence bug away from being wrong. - Allocating a new array unnecessarily. A working two-array solution exists (push evens then odds), but it costs O(n) extra space and obscures the two-pointer pattern that the follow-up is asking for.
- Returning a sorted version. The problem does NOT require numeric sorting within each partition. Returning
[2, 4, 1, 3]instead of[4, 2, 3, 1]is fully accepted; only the parity partitioning matters.
Solution Code