DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Sort Array By Parity II

EasyEditorial · 6 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 every valid answer can be built from mismatched parity lanes

An even index can hold only an even value, and an odd index can hold only an odd value. Think of the array as two lanes: positions 0, 2, 4 and so on are the even lane, while positions 1, 3, 5 and so on are the odd lane. A position that already contains the right parity needs no movement.

If an even-lane position contains an odd value, that value is misplaced. Because the array contains equally many even and odd values, some odd-lane position must contain an even value. Swapping those two mismatches fixes both positions at once. The pointers therefore skip correct positions and stop only at values that can repair each other.

An array split into even-index and odd-index lanesThe drawing shows an array of alternating even and odd index cells. An even pointer begins at index 0 and skips even values as it moves through indices 0, 2, 4 and so on. An odd pointer begins at index 1 and skips odd values as it moves through indices 1, 3, 5 and so on. The first remaining cells are an odd value in the even lane and an even value in the odd lane; exchanging them fixes both cells. The picture makes clear that correct positions are skipped and only a mismatched pair is swapped.1E !4O !6E3O8E5Oeven pointer0 → 2 → 4odd pointer1 → 3 → 54E1O6E3O8E5Ofirst odd valuefirst even valueE positions require even values; O positions require odd values012345 = n - 1swap the two first mismatches012345 = n - 1after the swap, both lanes have the required parity

Approach

  1. Set n to the array length and place i at index 0 for the even lane and j at index 1 for the odd lane, because every possible correct position belongs to one of these two parity classes.
  2. Advance i by 2 while nums[i] is even, because those even-lane positions already satisfy the requirement and checking them again cannot produce a useful swap.
  3. Advance j by 2 while nums[j] is odd, because those odd-lane positions are already correct and only an even value can repair a misplaced odd-lane position.
  4. If both pointers remain inside the array, swap nums[i] and nums[j], because the stopped values are an odd value in an even position and an even value in an odd position.
  5. Repeat the two scans after each swap, because fixing one pair may expose the next mismatched pair farther along each lane.
  6. Stop when either pointer reaches n and return the array, because the parity counts guarantee that no unmatched position can remain when all lane positions have been examined.

Complexityconstant working memory

MEASUREBOUNDWHY
TimeO(n)Each pointer moves only forward by steps of 2. A position is skipped once or participates in one swap, so the total number of pointer advances and value checks is at most proportional to n rather than n work per swap.
SpaceO(1) extraThe algorithm uses only n, i, and j in addition to the input array. The returned array is required output and is excluded from working memory. The bound does not degrade for any allowed arrangement because both pointers still move forward through their lanes only once.
Here, n is the number of elements in nums.

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

CPPScan the two parity lanes, then swap their first mismatches in place.
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int j = 1;

        while (i < n && j < n) {
            while (i < n && nums[i] % 2 == 0) {
                i += 2;
            }
            while (j < n && nums[j] % 2 == 1) {
                j += 2;
            }
            if (i < n && j < n) {
                swap(nums[i], nums[j]);
            }
        }

        return nums;
    }
};

The two inner loops are the core of the solution. They do not move by one because each pointer belongs to only one lane: i checks even indices and j checks odd indices. The boundary checks must remain inside both loops, since a pointer can reach n while searching for a mismatch. The outer condition then prevents any access after the search has run out of positions.

Common mistakestwo wrong pointer shapes that look almost correct

Previous · Sort Array by Parity