EasyCoding

Sort Array By Parity

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Clarify whether even and odd relative order must be preserved.
02For unordered output, keep pointers at the next even and odd positions.
03Advance satisfied pointers and swap misplaced values.
04Use a stable extra-array solution only when stability is required.

Reference answer

If the task only requires all even values before all odd values, use an in-place two-pointer partition. Set left=0 and right=n-1. Advance left while it points to an even value and decrement right while it points to an odd value. When both pointers are misplaced and left < right, swap them, then continue. The invariant is that all positions before left are even and all positions after right are odd. This handles negative integers too because in most languages parity should be checked with value % 2 === 0, not by assuming remainders are positive. It runs in O(n) time and O(1) extra space. If the prompt demands that the original order of evens and odds remain unchanged, this swapping method is invalid; collect evens then odds in a new array for O(n) extra space.

Then expect these follow-ups

How would you preserve relative order?
Tests: stability
What invariant proves the swaps correct?
Tests: partitioning

Hiring now

Get the Meta interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question