Sort Array By Parity — Editorial

Opening the reading…

Intuitionwhy partitioning is enough when internal order does not matter

The requirement only distinguishes two groups: even values belong on the left, and odd values belong on the right. Because neither group has an order requirement, you do not need to sort the values or preserve their original positions. You only need to find values that are on the wrong side of the boundary and exchange them.

Use one pointer from the left and one from the right. The left pointer skips values that are already even, while the right pointer skips values that are already odd. When both pointers stop, the left side contains an odd value and the right side contains an even value, so swapping them fixes both positions at once. Once the pointers meet, no unexamined pair remains.

Approach

Set left to the first index and right to the last index, because every position outside this interval has already been classified and needs no more work.

While left is smaller than right, inspect the two ends; stopping when they meet prevents unnecessary comparisons and avoids treating a single middle element as a pair.

If nums[left] is even, move left forward because that value already belongs in the left group and must not be swapped away.

Otherwise, if nums[right] is odd, move right backward because that value already belongs in the right group and the left odd value still needs a suitable partner.

If neither skip applies, nums[left] is odd and nums[right] is even, so swap them and move both pointers inward because both positions are now correct.

Return nums after the pointers meet, because every remaining position is either already on the correct side or is the single unpaired middle position.

Complexityeach pointer only moves inward

MEASURE	BOUND	WHY
Time	O(n)	Each pointer moves only inward, and together they pass over at most n positions. A value is inspected a constant number of times, so no index can cause repeated scanning.
Space	O(1)	The algorithm stores only left, right, and temporary swap state besides the input array. This remains constant even for the worst arrangement of values; the returned array is the modified input and is excluded from the extra-space bound.

Here n is the number of elements in nums. The returned array is required output and is excluded from extra space.

Annotated solutionC++ · in-place two-pointer partition

CPPScan inward, skip values already in the correct group, and swap the remaining misplaced pair.

#include <algorithm>
#include <vector>

using namespace std;

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

        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++;
            } else if (nums[right] % 2 == 1) {
                right--;
            } else {
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }

        return nums;
    }
};

The order of the three branches is what makes the loop easy to trust. First discard a correct left value; otherwise discard a correct right value; only when both values are misplaced do you swap. After the swap, both positions are settled, so advancing both pointers is safe. The method changes nums directly, which gives constant extra space while still returning the required array.