Back to solutions

Sort Colors

MediumArrays

Sort an array of 0s, 1s, and 2s in a single pass.

Open problem
Constraints
  • 1 <= n <= 300
  • nums[i] in {0, 1, 2}

Dutch national flag

Time O(n)Space O(1)

Keep three regions with pointers low, mid, high. Everything before low is 0, everything after high is 2, and low..mid-1 is 1. Scan with mid: a 0 swaps into the low region, a 2 swaps into the high region (without advancing mid), and a 1 just moves mid forward.

Key terms
three-way partition:
Splitting the array into less-than, equal, and greater-than regions in one pass.
Dutch national flag:
Dijkstra's algorithm for sorting three distinct values in O(n) time and O(1) space.
void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums[low++], nums[mid++]);
        else if (nums[mid] == 1) mid++;
        else swap(nums[mid], nums[high--]);
    }
}
Step by step
  1. Set low = 0, mid = 0, high = n-1.
  2. While mid <= high: if nums[mid] is 0, swap with low and advance both low and mid.
  3. If nums[mid] is 1, just advance mid.
  4. If nums[mid] is 2, swap with high and decrease high (do not advance mid yet, the swapped value is unexamined).