DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Sort Array By Parity

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

an array partitioned by two pointersA row of array cells contains mixed even and odd integers. A left pointer begins at the first cell and moves right over even values. A right pointer begins at the last cell and moves left over odd values. The remaining highlighted pair is an odd value on the left and an even value on the right; swapping that pair places both values in the correct group. The picture makes the two pointers' different skip rules visible.2467813119L skips evens →R skips odds ←L stops: odd 7R stops: even 8wrong-side pairswap 7 ↔ 8The stops expose an odd-left / even-right pair to exchange.

Approach

  1. 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.
  2. 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.
  3. If nums[left] is even, move left forward because that value already belongs in the left group and must not be swapped away.
  4. 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.
  5. 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.
  6. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(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.

Common mistakestwo wrong code shapes that change the partition

Previous · Merge Sorted Array