[/dsa/leetcode]

75 - Sort Colors

Wednesday, 16 September 2026

<medium> [problem]

Dutch National Flag - three pointers carving the array into a 0 region, a 1 region, an unknown middle and a 2 region, in one pass.

{array}{two pointers}{sorting}

Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

You must solve this problem without using the library’s sort function.

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2

Follow-up: could you come up with a one-pass algorithm using only constant extra space?

Approach

With only three distinct values, counting beats comparing. Tally how many 0s, 1s and 2s there are, then overwrite the array with that many of each - O(n) time, O(1) space, and no comparisons at all. That is a perfectly good answer, but it reads the array twice, and the follow-up asks for one pass.

Doing it in a single pass means maintaining, at every moment, a partition of the array into four regions. Three indices mark the boundaries:

[0, low)      all 0s
[low, mid)    all 1s
[mid, high]   unknown, not looked at yet
(high, n)     all 2s

The unknown region shrinks from the front as mid advances and from the back as high retreats, and the loop runs while it is non-empty. Look at nums[mid] and restore the invariant:

  • 0 — it belongs at the front. Swap it with nums[low], then advance both low and mid.
  • 1 — it is already in the right region, since the 1s live immediately before mid. Just advance mid.
  • 2 — it belongs at the back. Swap it with nums[high] and shrink high.
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[mid++], nums[low++]);
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[high--]);
            }
        }
    }
};

The asymmetry between the two swap branches is the whole trick, and it is the part to be able to justify:

  • Swapping with low also advances mid, because whatever comes back is known. Either low == mid and nothing moved, or low < mid, which means the region between them is all 1s, so a 1 lands at mid — already correct, nothing to re-examine.
  • Swapping with high does not advance mid, because whatever comes back is from the unknown region and could be any of the three values. It has to be looked at on the next iteration.

Advancing mid in the 2 branch is the standard bug here, and it silently drops values past the partition.

nums = [2, 0, 2, 1, 1, 0]      low mid high
                                0   0   5    nums[mid]=2  swap with high
       [0, 0, 2, 1, 1, 2]       0   0   4    nums[mid]=0  swap with low
       [0, 0, 2, 1, 1, 2]       1   1   4    nums[mid]=0  swap with low
       [0, 0, 2, 1, 1, 2]       2   2   4    nums[mid]=2  swap with high
       [0, 0, 1, 1, 2, 2]       2   2   3    nums[mid]=1  mid++
       [0, 0, 1, 1, 2, 2]       2   3   3    nums[mid]=1  mid++
       [0, 0, 1, 1, 2, 2]       2   4   3    mid > high, stop
  • time: O(n) — each iteration either advances mid or retreats high, so the unknown region shrinks every step
  • space: O(1) — three indices

The termination argument is worth stating separately from the correctness one: the loop makes no progress on the array in the 2 branch, but it always shrinks the window, so it cannot spin.

This generalises past three colors — it is really “partition around a pivot value into less, equal and greater”, which is exactly the three-way partition that makes quicksort handle duplicate-heavy input well.

quantinium © 2026