Sort Array By Parity II — Editorial

Opening the reading…

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.

Approach

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.

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.

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.

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.

Repeat the two scans after each swap, because fixing one pair may expose the next mismatched pair farther along each lane.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(1) extra	The 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.