Sort Colors — Editorial

Opening the reading…

Intuitionthe array is sorted by maintaining regions, not by comparing every pair

Because every value is 0, 1, or 2, a sorted result has a rigid shape: all 0s come first, then all 1s, then all 2s. You do not need to decide the order between arbitrary values. You only need to place each encountered value into its matching region while keeping the unprocessed values available for inspection.

Keep low at the first position that is not known to be a 0, mid at the first position not yet classified, and high at the last position that is not known to be a 2. Values before low are 0, values from low through mid - 1 are 1, and values after high are 2. When mid sees a 2, swap it with high but do not advance mid: the incoming value has not been classified yet.

The invariant behind the Dutch national flag scan.

Approachclassify the value at mid and move only the boundary that the value justifies

Initialise low and mid to 0 and high to n - 1, because no positions are classified before the scan and the unknown region must cover the entire array.

Continue while mid <= high, because every index through high is still unknown and the scan is complete only when that region becomes empty.

When nums[mid] is 0, swap it with nums[low], then increment both low and mid, because the 0 belongs at the end of the 0 region and the value moved to mid was already in the classified left portion.

When nums[mid] is 1, increment mid only, because 1 already belongs between the 0 region and the unknown region and needs no swap.

When nums[mid] is 2, swap it with nums[high] and decrement high, because the 2 is now fixed at the right edge, but the value brought into mid is new and must be examined before mid can move.

Return after the loop without another pass, because every index before low is 0, every index from low through mid - 1 is 1, and every index after high is 2.

Complexityconstant working memory and one visit per boundary movement

MEASURE	BOUND	WHY
Time	O(n)	mid never moves left, high only moves left, and low only moves right. Each loop either advances mid or decreases high, so there are at most n advances of mid plus n decreases of high rather than repeated scans of the same unknown values.
Space	O(1) extra	Only the three indices and a constant number of temporary values are used; nums is modified in place. The bound stays O(1) even for the worst input shape, such as all 0s, all 1s, or all 2s.

Here n means the number of elements in nums. The returned value is void, so there is no output array whose storage needs to be counted.

Annotated solutionC++ · one pass · Dutch national flag partition

CPPPartition the array into confirmed 0s, 1s, unknown values, and confirmed 2s in one scan.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = static_cast<int>(nums.size()) - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

The most important placement is the missing mid++ in the 2 branch. Swapping with high places the current 2 correctly, but high's old value arrives at mid from the unknown region. The loop must inspect that incoming value next. In contrast, the value swapped into mid from low is already known to be a 1 or a 0-region value, so the 0 branch can safely advance both indices.

The counting alternativesimpler when the single-pass requirement is relaxed

CPPCount each color, then overwrite the input with the required runs.

#include <vector>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0, 0, 0};

        for (int value : nums) {
            count[value]++;
        }

        int index = 0;
        for (int color = 0; color <= 2; color++) {
            for (int copies = 0; copies < count[color]; copies++) {
                nums[index] = color;
                index++;
            }
        }
    }
};

Counting is a reasonable arrangement when the problem allows two passes: one pass counts values and a second pass writes the three runs. It still uses O(1) extra space and O(n) time, but it violates this problem's single-pass requirement and temporarily discards the original arrangement. The three-region scan buys compliance with that requirement while preserving the same asymptotic bounds.