[LeetCode] 905. Sort Array By Parity
1 min read
🧠 Remember: “Evens left, odds right.”
The problem — 20 seconds
[3, 1, 2, 4] → [4, 2, 1, 3] (any evens-first order counts).
Return the array with every even before every odd. Within-group order does not matter — [2, 4, 3, 1] and [4, 2, 1, 3] both pass.
Each pointer hunts what does not belong on its side:
L=0(3 odd ✗) R=3(4 even ✗) → swap → [4,1,2,3]
L=1(1 odd ✗) R=2(2 even ✗) → swap → [4,2,1,3]
L=2 R=1 → crossed → stop, evens [4,2] leftThat is the whole algorithm. Everything below just makes it obvious why.
Your first instinct
Filter twice and concatenate:
return [x for x in nums if x % 2 == 0] + [x for x in nums if x % 2 == 1]Correct order, wrong budget — two passes plus a full-size new list. A single-scan write-index partitioner fixes the space but hides the problem’s symmetry.
The turning point
Evens belong left, odds belong right — so each side knows its misfit. L walks past evens until it sticks on an odd; R walks past odds until it sticks on an even. Both stuck? They are each other’s fix: swap and close in.
Watch it work
Press Play. Each pointer skips what is already home — L glides over evens, R over odds — and only stuck misfits ever swap.
Interactive visual · Partition Patrol
Can you split evens from odds?
L hunts an odd from the left, R hunts an even from the right. Swap the misfits and close in — evens end up left, odds right.
L, R = 0, n-1skip evens at L, odds at Rif L<R: swap; L+=1; R-=1Quick check — make it stick
What does L walk past without stopping?
🧠 Memory hook: “Evens left, odds right.” Each pointer skips what is already home and only the two misfits swap.
What the code is really saying
from typing import List
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
while left < right and nums[left] % 2 == 0:
left += 1
while left < right and nums[right] % 2 == 1:
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return numsRead it as the visual: skip-home loops, then one misfit swap. The inner left < right guards keep the pointers from crossing mid-skip on inputs like [] or [0].
Why it works
Invariant: left of L is even, right of R is odd, the middle is undecided. Skips shrink the middle for free; swaps fix two cells. Pointers only move inward, so the regions end adjacent.
n = 4 → 2 swaps, in place
Time O(n), space O(1).🧠 Remember
Sort Array By Parity → “Evens left, odds right.” Skip what is home; swap only the two misfits.
🔁 Try this: Move Zeroes? (Hint: same border instinct, but only one side has a rule — non-zeroes pack left.)
Related: Two Sum · 3Sum · Move Zeroes