Module 04 · Two Pointers and In-Place Read/Write State

040. Partition Evens Before Odds

Interview · Download this solution · All solutions and shared helpers

Problem

Rearrange an integer list in place so every even value precedes every odd value. Relative order within either category is not required. Return the same list using the deterministic inward scan shown here. Negative values use Python's modulo parity rule.

Examples

Example 1

evens_before_odds([3, 1, 2, 4])
=> [4, 2, 1, 3]

This scan produces a valid, deliberately unstable partition.

Example 2

evens_before_odds([])
=> []

The region is empty.

Example 3

evens_before_odds([-3, -2, 0])
=> [0, -2, -3]

Zero and negative even values belong on the left.

Reveal the worked solution and reasoning

Why this mechanism works

An even value at the left frontier is already on the correct side; an odd value at the right frontier is likewise final. When both are misplaced, swap them. Unlike stable filtering, this contract permits exchanges across the list.

State and boundaries

Positions before left are even; positions after right are odd. The inclusive interior is unclassified.

Protocol

Advance left across already-correct even values.
Retreat right across already-correct odd values.
Swap the two misplaced endpoints if distinct.
Shrink both frontiers after a swap.

Visualization

[even prefix | unknown | odd suffix]
wrong left: odd <-> even :wrong right
exchange finalizes both endpoints

Python implementation

def evens_before_odds(nums):
    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 != 0:
            right -= 1
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    return nums

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

evens_before_odds([3, 1, 2, 4])

L2 evens_before_odds: left, right = 0, len(nums) - 1
nums=[3, 1, 2, 4]; left=0; right=3

L9 evens_before_odds: nums[left], nums[right] = nums[right], nums[left]
nums=[4, 1, 2, 3]; left=0; right=3

L10 evens_before_odds: left += 1
nums=[4, 1, 2, 3]; left=1; right=3

L11 evens_before_odds: right -= 1
nums=[4, 1, 2, 3]; left=1; right=2

L9 evens_before_odds: nums[left], nums[right] = nums[right], nums[left]
nums=[4, 2, 1, 3]; left=1; right=2

L10 evens_before_odds: left += 1
nums=[4, 2, 1, 3]; left=2; right=2

L11 evens_before_odds: right -= 1
nums=[4, 2, 1, 3]; left=2; right=1

Result: [4, 2, 1, 3]. This scan produces a valid, deliberately unstable partition.

evens_before_odds([])

L2 evens_before_odds: left, right = 0, len(nums) - 1
nums=[]; left=0; right=-1

Result: []. The region is empty.

Why the solution is correct

Skipping finalizes correctly classified values. A swap places an even value on the left and an odd value on the right, preserving the region claims. The unclassified region shrinks until it has at most one cell, which lies at the partition boundary.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

A stable expected output is too strict for this contract. Every skip loop still needs a crossing check.

Reasoning card

State: Positions before left are even; positions after right are odd. The inclusive interior is unclassified.

Invariant: Everything left of left is even; everything right of right is odd.

Decision to rehearse: Skip already-correct values before swapping.

Finish: Shrink both frontiers after a swap

Transfer exercise

Require stability. Compare a new-array solution with more complicated constant-space approaches rather than assuming the same swaps remain valid.