What is the brute force approach and complexity for Sort Array By Parity?

Two passes into a new array: first all evens, then all odds with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Sort Array By Parity?

L looks for an odd, R looks for an even, swap them; O(1) extra space with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Sort Array By Parity?

Look for key signals in the prompt: "all even numbers, then all odd numbers" indicates Every number falls into one of a few fixed groups, and the groups have a fixed order → partition.; "any order is accepted" indicates We don't need to keep the original order inside a group, so swapping (which mixes up the order) is allowed.; "rearrange the array" indicates We can do it in place: keep each finished group behind its own pointer..

Sort Array By Parity

Easy·LeetCode #905Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTwo Pointers (Partition, two regions)

Complexity:O(N)→O(N)

Key Insight

Keep L at the left end and R at the right end. Everything left of L is a finished even, everything right of R is a finished odd, and the middle is unchecked. If nums[L] is even, it is already home, so move L right. If nums[R] is odd, it is already home, so move R left. Otherwise L is on an odd and R is on an even — swap them, and both are now home. Stop when the pointers meet.

Core Validity Invariant

At every moment, nums[0..L-1] are all even and nums[R+1..n-1] are all odd; only the middle nums[L..R] is still unknown. When the middle is empty, the whole array is arranged.

Problem

You are given an integer array nums.

Rearrange it so that all even numbers come first, followed by all odd numbers. Return the rearranged array.

The order inside the even group and inside the odd group does not matter. Any arrangement with every even before every odd is accepted.

Input

An integer array nums.

Output

An array with the same numbers, where every even number comes before every odd number.

Example 1

Input: nums = [3, 1, 2, 4]

Output: [2, 4, 3, 1]

2 and 4 are even, 3 and 1 are odd. [4, 2, 3, 1], [2, 4, 1, 3] and [4, 2, 1, 3] are also accepted.

Example 2

Input: nums = [0]

Output: [0]

One number is already arranged. (0 is even.)

Constraints

• 1 ≤ nums.length ≤ 5000
• 0 ≤ nums[i] ≤ 5000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
How many different kinds of numbers are there, as far as this problem cares?
2.
Does the order inside the even group matter? What freedom does that give me?
3.
If I build a brand-new array, how would I fill it?
4.
Where does an even number belong — near the left end or the right end? And an odd one?
5.
If I find a number that is on the wrong side, where could I find a partner to swap it with?

Brute force approach

Idea

Make a new empty array. Walk through nums once and copy every even number. Walk through it a second time and copy every odd number. The new array is the answer.

Thinking process

1
The answer is just "the evens, then the odds".
2
The simplest way to build that is literally in that order: collect the evens first.
3
Then go through the input again and collect the odds.
4
This even keeps the original order inside each group, which the problem does not require.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        vector<int> result;
        result.reserve(nums.size());

        // Pass 1: copy every even number.
        for (int x : nums) {
            if (x % 2 == 0) result.push_back(x);
        }
        // Pass 2: copy every odd number after them.
        for (int x : nums) {
            if (x % 2 != 0) result.push_back(x);
        }
        return result;
    }
};

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int[] result = new int[nums.length];
        int idx = 0;

        // Pass 1: copy every even number.
        for (int x : nums) {
            if (x % 2 == 0) {
                result[idx++] = x;
            }
        }
        // Pass 2: copy every odd number after them.
        for (int x : nums) {
            if (x % 2 != 0) {
                result[idx++] = x;
            }
        }
        return result;
    }
}

class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        result: list[int] = []

        # Pass 1: copy every even number.
        for x in nums:
            if x % 2 == 0:
                result.append(x)

        # Pass 2: copy every odd number after them.
        for x in nums:
            if x % 2 != 0:
                result.append(x)

        return result

export function sortArrayByParity(nums: number[]): number[] {
    const result: number[] = [];

    // Pass 1: copy every even number.
    for (const x of nums) {
        if (x % 2 === 0) result.push(x);
    }
    // Pass 2: copy every odd number after them.
    for (const x of nums) {
        if (x % 2 !== 0) result.push(x);
    }
    return result;
}

Complexity

Time O(N)Space O(N)

The time is already as good as it gets — we must look at every number. The only cost is the second array of size n. Can we rearrange nums itself instead?

Optimized approach

Idea

Start from brute force

Brute force reads the array twice and writes every number into a second array, just to put each number on the correct side.

Find the repeated work

There is no repeated work in time — the waste is space. Most numbers may already be on the correct side. Only the ones on the wrong side need to move, and each wrong-side even can trade places with a wrong-side odd.

Define the state — what variables do I need?

L: Everything before L (`nums[0..L-1]`) is even and finished. L is the next cell to check from the left.
R: Everything after R (`nums[R+1..n-1]`) is odd and finished. R is the next cell to check from the right.
nums[L..R]: The unchecked middle. It shrinks by at least one every step.

Define validity

At every moment, nums[0..L-1] are all even and nums[R+1..n-1] are all odd; only the middle nums[L..R] is still unknown. When the middle is empty, the whole array is arranged.

Define the transitions — when does each pointer move, and why is it safe?

nums[L] is even

L++

An even number belongs on the left, so it can join the finished evens region as it is.

nums[L] is odd and nums[R] is odd

R--

The odd at R is already on the correct side, so it joins the finished odds region. L keeps waiting for a partner.

nums[L] is odd and nums[R] is even

swap(nums[L], nums[R]); L++; R--

Both numbers are on the wrong side. After one swap the even is on the left and the odd is on the right, so both regions grow by one.

L ≥ R

Stop

There is at most one unchecked cell left, and a single number is fine wherever it sits.

What does the current window add to the answer?

Each step puts at least one more number into a finished region (and a swap finishes two at once). When the regions touch, every number is in a finished region.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;

        // Invariant: nums[0 .. left-1] are all even,
        //            nums[right+1 .. n-1] are all odd,
        //            nums[left .. right] is not checked yet.
        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++;                 // already on the correct side
            } else if (nums[right] % 2 != 0) {
                right--;                // already on the correct side
            } else {
                // Odd on the left, even on the right: both are wrong, so swap.
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }
        return nums;
    }
};

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;

        // Invariant: nums[0 .. left-1] are all even,
        //            nums[right+1 .. n-1] are all odd,
        //            nums[left .. right] is not checked yet.
        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++; // already on the correct side
            } else if (nums[right] % 2 != 0) {
                right--; // already on the correct side
            } else {
                // Odd on the left, even on the right: both are wrong, so swap.
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        left, right = 0, len(nums) - 1

        # Invariant: nums[0 .. left-1] are all even,
        #            nums[right+1 .. n-1] are all odd,
        #            nums[left .. right] is not checked yet.
        while left < right:
            if nums[left] % 2 == 0:
                left += 1  # already on the correct side
            elif nums[right] % 2 != 0:
                right -= 1  # already on the correct side
            else:
                # Odd on the left, even on the right: both are wrong, so swap.
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        return nums

export function sortArrayByParity(nums: number[]): number[] {
    let left = 0;
    let right = nums.length - 1;

    // Invariant: nums[0 .. left-1] are all even,
    //            nums[right+1 .. n-1] are all odd,
    //            nums[left .. right] is not checked yet.
    while (left < right) {
        if (nums[left] % 2 === 0) {
            left++; // already on the correct side
        } else if (nums[right] % 2 !== 0) {
            right--; // already on the correct side
        } else {
            // Odd on the left, even on the right: both are wrong, so swap.
            const temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    return nums;
}

Complexity

Time O(N)Space O(1)

Every step moves at least one pointer inward, so there are at most n steps. No extra array is used.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Two passes into a new array: first all evens, then all odds	O(N)	O(N)
Optimal	L looks for an odd, R looks for an even, swap them; O(1) extra space	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“all even numbers, then all odd numbers”Every number falls into one of a few fixed groups, and the groups have a fixed order → partition.
“any order is accepted”We don't need to keep the original order inside a group, so swapping (which mixes up the order) is allowed.
“rearrange the array”We can do it in place: keep each finished group behind its own pointer.

Two fixed categories+order inside a group doesn't matter+rearrange in place→Two Pointers (Partition, two regions)

This is the anchor of the partition family. There is no sorting by value here — only which group a number is in. Learn the region idea: each finished group lives behind its own pointer, and the unchecked numbers sit in the middle. Sort Colors adds a third group (and a third pointer). Partition Array According to Given Pivot also has three groups, but there the order inside each group must be kept, which rules out swapping.

Don't make this mistake

Pattern confusion: sorting the array

✗ sort(nums.begin(), nums.end());

✓ Partition by parity with two pointers (or two passes).

Sorting by value does not group by parity: [3, 1, 2, 4] sorted is [1, 2, 3, 4], which mixes evens and odds. And even a sort with a parity comparator costs O(N log N) for a job that needs one O(N) pass. This is a partition problem (put each number in its group), not a sorting problem.

Moving the pointers after the swap only sometimes

✗ swap(nums[left], nums[right]); // forgot left++ / right--

✓ swap(nums[left], nums[right]); left++; right--;

Without moving, the loop still works but wastes steps re-checking the two numbers it just fixed. Worse, in versions where the checks are written as two separate while loops, forgetting to move can cause an infinite loop. After a swap, both cells are finished — move past them.

Missing the bounds check in inner loops

✗ while (nums[left] % 2 == 0) left++;

✓ while (left < right && nums[left] % 2 == 0) left++;

If the array is all even, left runs past the end of the array. Always keep left < right inside every inner loop.

Checking odd with `x % 2 == 1` when negatives are possible

In C++, -3 % 2 is -1, not 1. The constraints here say nums[i] ≥ 0, so == 1 happens to work, but x % 2 != 0 is the habit that is always correct.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Sort Colors