Sort Array By Parity: Two-Pointer Partition

Given an integer array nums, move all even integers to the beginning of the array followed by all odd integers. You can return any answer that satisfies this condition.

This is LeetCode 905: Sort Array By Parity, an easy problem that introduces the two-pointer partition pattern. The trick is recognizing that you do not need to sort anything. You just need to separate two groups, and a pair of converging pointers does this in a single pass with no extra memory.

Why this problem matters

Sort Array By Parity is the simplest version of a partition problem. You have one condition (even vs. odd) and you need to rearrange elements so that everything satisfying the condition comes first. This exact structure appears in quicksort's partition step, in the Dutch National Flag problem (Sort Colors), and in problems like Move Zeroes where you push certain elements to one end.

The two-pointer partition is one of the most reusable patterns in array manipulation. Once you internalize how two pointers converge from both ends and swap misplaced elements, you can apply the same logic to harder problems with barely any modification. The partition condition changes, but the mechanics stay the same.

Understanding this problem deeply also builds your intuition for in-place algorithms. Many candidates reach for extra arrays or filter operations when a simple swap would do. Recognizing that you can solve partition problems in O(1) space is a signal of algorithmic maturity.

The brute force approach

The most obvious approach is to create two separate lists: one for even numbers and one for odd numbers, then concatenate them.

def sortArrayByParity(nums):
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 != 0]
    return evens + odds

This works and is easy to understand. You scan the array twice (once for evens, once for odds) and build a new array. The time is O(n) and the space is O(n) because you are creating a new list of the same size. For an interview, this is a fine starting point, but the interviewer will ask if you can do it in-place.

The key insight

You do not need a second array. Place one pointer at the start (left) and one at the end (right). The left pointer searches for an odd number that is out of place. The right pointer searches for an even number that is out of place. When both find a misplaced element, swap them and move inward.

This works because you are partitioning into exactly two groups. Every swap fixes two elements at once: the odd number moves to the right side where it belongs, and the even number moves to the left side where it belongs. After enough swaps, the pointers meet in the middle and every element is on the correct side.

Walking through it step by step

Let's trace through nums = [3, 1, 2, 4] using the two-pointer approach.

Two swaps and we are done. The pointers crossed after processing all four elements. Notice that the relative order within evens or odds is not preserved, but the problem does not require that. Any valid partition is accepted.

The solution

def sortArrayByParity(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] % 2 == 0:
            left += 1
        elif nums[right] % 2 == 1:
            right -= 1
        else:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    return nums

Here is what each piece does:

1. left starts at index 0 and right starts at the last index. They converge toward the center.
2. If nums[left] is already even, it is in the correct zone. Advance left to find the next candidate for swapping.
3. If nums[right] is already odd, it is in the correct zone. Move right leftward to find the next candidate.
4. If nums[left] is odd and nums[right] is even, both are on the wrong side. Swap them and move both pointers inward.
5. When left meets or passes right, every element is on the correct side.

Complexity analysis

This is optimal. You must inspect each element at least once to know its parity, so O(n) is the lower bound. And O(1) space means no auxiliary data structures beyond the two index variables.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Two-pointer partition

The pattern of using two converging pointers to separate elements into two groups in-place:

left, right = 0, len(arr) - 1
while left < right:
    if left_element_is_correct:
        left += 1
    elif right_element_is_correct:
        right -= 1
    else:
        swap(left, right)
        left += 1
        right -= 1

In Sort Array By Parity, the condition is even vs. odd. In quicksort's partition, the condition is less than vs. greater than the pivot. In problems like segregating 0s and 1s, the condition is the binary value itself. The skeleton is the same: two pointers converge, each advancing past correctly-placed elements, swapping when both find something wrong.

2. In-place rearrangement

The pattern of modifying an array without allocating additional storage proportional to the input size:

for i in range(len(arr)):
    if condition(arr[i]):
        swap_or_overwrite(arr, i, target_position)
        update_target_position()

In Sort Array By Parity, swaps between the two ends accomplish the rearrangement. In Move Zeroes, a write pointer fills non-zero values from the front. In Remove Element, a slow pointer tracks the position for the next valid element. The core idea is the same: use pointer arithmetic to place elements where they belong without copying the whole array.

Edge cases

Before submitting, make sure your solution handles these:

• All even [2, 4, 6, 8]: left pointer advances all the way without any swaps. Returns the array unchanged.
• All odd [1, 3, 5, 7]: right pointer retreats all the way without any swaps. Returns the array unchanged.
• Single element [1] or [2]: left starts equal to right, so the while loop never executes. Returns as-is.
• Already partitioned [2, 4, 1, 3]: left advances past 2 and 4, right retreats past 3 and 1, pointers cross without swapping.
• Empty array []: no elements to process. Returns empty.
• Alternating parity [1, 2, 3, 4]: requires the maximum number of swaps. Each element ends up on the opposite side.

The two-pointer solution handles all of these without special-case logic.

Common mistakes

1. Using extra space when it is not needed. Creating a new array with list comprehensions works but misses the point. The interviewer wants to see you solve it in O(1) space.

2. Advancing both pointers unconditionally after a swap. This is actually correct here, but forgetting to advance them causes an infinite loop. After a swap, both elements are now correctly placed, so both pointers should move.

3. Using left <= right instead of left < right. When left == right, there is one element left and it does not matter which side it is on (it is already in the middle). Using <= does not cause errors here, but it adds an unnecessary iteration.

4. Trying to preserve relative order. The problem does not require stability. If you try to maintain the original order of even or odd elements, you will overcomplicate the solution. A simple swap-based partition is sufficient.

From understanding to recall

You have read the two-pointer partition and it clicks. Left pointer, right pointer, swap when both are wrong, advance when correct. Simple. But simplicity is deceptive. In an interview, you still need to write the exact while-loop condition, get the parity checks right, and remember to advance both pointers after the swap.

These details are easy to second-guess under pressure. Did I use left < right or left <= right? Do I move both pointers after swapping, or just one? Do I check nums[left] % 2 == 0 or nums[left] % 2 != 0? Each question costs time and confidence in a timed setting.

Spaced repetition eliminates that hesitation. You write the two-pointer partition from scratch at increasing intervals until the code flows from muscle memory. After a few rounds, you see "separate elements by condition in-place" and the entire solution appears without thinking. The pattern becomes automatic, and you can spend your interview time on communication rather than reconstruction.

Related posts

• Sort Colors - Dutch National Flag partition with three categories
• Move Zeroes - Two-pointer partition moving zeroes to the end
• Remove Element - In-place element removal using two pointers

CodeBricks breaks the Sort Array By Parity LeetCode problem into its two-pointer partition and in-place rearrangement building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a partition question shows up in your interview, you do not think about it. You just write it.