Sort Array By Parity II: Two-Pointer Placement

LeetCode 922, Sort Array By Parity II, is an easy problem that asks you to rearrange an array so that elements at even indices are even and elements at odd indices are odd. Half the elements in the input are even and half are odd, so a valid arrangement always exists.

The problem

Given an array nums of length n where exactly half the elements are even and half are odd, rearrange it so that nums[i] is even when i is even, and nums[i] is odd when i is odd. You can return any valid answer.

Input:  [4, 2, 5, 7]
Output: [4, 5, 2, 7]

Index 0 and 2 are even positions and must hold even values. Index 1 and 3 are odd positions and must hold odd values. The input has two even numbers (4, 2) and two odd numbers (5, 7), so we just need to place them in the right slots.

Why this problem matters

This problem teaches a clean two-pointer technique where each pointer is responsible for one "type" of position. Instead of sorting the entire array, you only fix elements that are in the wrong spot. The two pointers move independently through even and odd indices respectively, and when both find a misplaced element, a single swap fixes both.

This pattern generalizes to any situation where you need to partition elements into alternating categories in-place. It also shows that you do not need to compare elements against each other, only against a property (parity) that determines their correct position.

The brute force approach

The simplest method is to separate even and odd numbers into two lists, then interleave them:

def sortArrayByParityII(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    result = [0] * len(nums)
    for i in range(len(evens)):
        result[2 * i] = evens[i]
        result[2 * i + 1] = odds[i]
    return result

This works and runs in O(n) time, but it uses O(n) extra space for the two lists and the result array. You can do better by working in-place.

The key insight

Use two pointers: one that scans even indices (0, 2, 4, ...) and one that scans odd indices (1, 3, 5, ...). The even pointer looks for an odd number sitting at an even index. The odd pointer looks for an even number sitting at an odd index. When both pointers find a misplaced element, swap those two elements. The swap fixes both positions at once because you are moving an odd number to an odd index and an even number to an even index.

Walking through it step by step

The solution

def sortArrayByParityII(nums):
    j = 1
    for i in range(0, len(nums), 2):
        if nums[i] % 2 == 1:
            while nums[j] % 2 == 1:
                j += 2
            nums[i], nums[j] = nums[j], nums[i]
    return nums

Here is what each piece does:

1. j = 1 initializes the odd pointer at index 1, the first odd position.
2. for i in range(0, len(nums), 2) iterates through all even indices.
3. if nums[i] % 2 == 1 checks whether an odd number is sitting at an even index. If so, it needs to be moved.
4. while nums[j] % 2 == 1 advances the odd pointer until it finds an even number at an odd index. That even number is also misplaced.
5. nums[i], nums[j] = nums[j], nums[i] swaps the two misplaced elements. The odd number goes to an odd index, and the even number goes to an even index.
6. return nums returns the modified array in-place.

The odd pointer j never resets. It only moves forward. Since there are exactly as many misplaced even-at-odd as misplaced odd-at-even, the two pointers always find matching pairs.

Complexity analysis

Each pointer traverses its respective set of indices at most once. The even pointer visits every even index exactly once. The odd pointer visits each odd index at most once (it never backtracks). Total work is proportional to n. The algorithm modifies the array in-place with only a constant number of extra variables.

Building blocks

1. Two-pointer placement by property

The core pattern is two independent pointers, each scanning a subset of positions for elements with the wrong property:

j = start_b
for i in range(start_a, n, step_a):
    if wrong_property(nums[i]):
        while not wrong_property_b(nums[j]):
            j += step_b
        nums[i], nums[j] = nums[j], nums[i]

This generalizes beyond parity. Any time you need to place elements into alternating slots based on a binary property, this pattern applies. The key invariant is that the number of misplaced elements on each side is always equal, so the pointers stay in sync.

2. In-place swap to fix two violations

A single swap corrects two positions simultaneously. This works whenever two elements are each in a position meant for the other type. Recognizing this "dual fix" property is what makes the O(1) space solution possible. Without it, you would need auxiliary storage to track pending placements.

Edge cases

Before submitting, verify your solution handles:

• Already sorted like [2, 1, 4, 3]: every element is in the right spot. The even pointer never enters the if-block, and no swaps occur.
• Completely swapped like [1, 2, 3, 4]: every even index has an odd number and every odd index has an even number. Maximum swaps needed (n/2 swaps for an array of length n).
• Length 2 like [1, 2] or [2, 1]: the minimum non-trivial case. At most one swap.
• Large values: parity is determined by % 2, so values up to 10^9 work fine without overflow concerns in Python.
• All same parity at wrong positions: like [1, 4, 3, 2] where both even-indexed positions hold odd values. Both must be swapped, and the odd pointer finds both even values at odd positions.

From understanding to recall

You have seen how two pointers, one walking even indices and one walking odd indices, fix every parity violation with a single pass and no extra space. The logic is minimal: scan, detect, swap. But reproducing it under pressure means remembering which pointer starts where, which direction each moves, and what condition triggers the swap.

Spaced repetition locks these details in. The first review might feel easy since you just read through it. But when the problem resurfaces three days later, you will notice which parts you actually retained and which slipped. Did you remember that j never resets? Did you remember to advance j by 2, not by 1? These are the small details that spaced repetition drills into long-term memory.

By the time you see this pattern in an interview, whether it is parity, positive/negative alternation, or any binary property placement, the two-pointer template will feel automatic.

Related posts

• Sort Array By Parity - The simpler variant where you just need all evens before all odds, without alternating positions
• Two Sum II - Another two-pointer technique on arrays, using convergence from both ends
• Move Zeroes - In-place element placement using a write pointer, a close relative of the swap-based approach

CodeBricks drills the two-pointer placement pattern as a standalone building block. You practice detecting misplaced elements and swapping them in-place until the technique becomes second nature. When a variant appears in an interview, you recognize the shape immediately and write the solution without hesitation.