#905
Sort Array By Parity
Easy Two-way partition
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rearrange the array so all even numbers come before all odd numbers. Any order inside each group is fine.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: evens first, odds after, any order inside.
Why this works: a boundary marks the end of the even zone; every even number found is swapped into it.
Example: [3, 1, 2, 4]
3 odd, 1 odd2 even → swap to index 0 → [2, 1, 3, 4]4 even → swap to index 1 → [2, 4, 3, 1]
✦Hints open one at a time
This is the two-colour version of the Dutch National Flag.
Keep a boundary: everything before it is even.
↗Approach
Scan with i; whenever nums[i] is even, swap it to the boundary and grow the boundary.
</>Solution (Java)
class Solution {
public int[] sortArrayByParity(int[] nums) {
int even = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] % 2 == 0) {
int t = nums[even];
nums[even++] = nums[i];
nums[i] = t;
}
}
return nums;
}
}!Common mistake
Creating two lists and joining them — fine, but uses O(n) space for no reason.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon