Sort Colors — Dutch National Flag Three-Pointer [LC 75, Microsoft, Facebook]

Problem Statement#

LeetCode 75 — Sort Colors · Difficulty: Medium

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

You must solve this without using the library's sort function. Use only constant extra space.

Constraints:

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

Example 1:

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

Example 2:

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

Example 3:

Input:  nums = [0]
Output: [0]

Why This Problem Matters#

LC 75 (Sort Colors) is the canonical Dutch National Flag problem, designed by Edsger Dijkstra. Microsoft, Facebook, and Amazon ask it because it tests in-place array manipulation, three-region invariant reasoning, and the ability to handle an asymmetric swap (when mid swaps with hi, we do not advance mid — explaining why is the interview's core moment).

The naive approach — count each color and overwrite — is O(n) and technically correct, but it requires two passes and does not generalize. The Dutch National Flag algorithm is a single-pass, O(1) space, in-place sort that demonstrates deep understanding of pointer invariants.

The problem also teaches a general pattern: partitioning an array into three regions using three pointers is a building block for the three-way partition in quicksort, which handles arrays with many duplicates far better than standard two-way partition.

The Core Insight#

Maintain three pointers and three invariants simultaneously:

mid is the "cursor" that scans through the unknown region. For each element:

• nums[mid] == 0: swap with nums[lo], advance both lo and mid (the swapped element is a 1 or a 0 we already processed).
• nums[mid] == 1: mid is already in the right zone; just advance mid.
• nums[mid] == 2: swap with nums[hi], decrement hi. Do not advance mid because the swapped-in element is unknown.

The loop ends when mid > hi (unknown region is empty).

Visual Dry Run#

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

lo=0, mid=0, hi=5

Result: [0, 0, 1, 1, 2, 2] ✓

Common Mistakes#

1. Advancing mid after swapping with hi. When you swap nums[mid] (a 2) with nums[hi] (unknown), the element that lands at mid has not been inspected yet. Advancing mid skips it. Only advance mid when you swap with lo (you know what came from lo) or when nums[mid] == 1.

2. Using mid < hi instead of mid <= hi in the loop condition. When mid == hi, that element is still in the unknown region and must be processed. Using mid < hi stops one step early and leaves one element unsorted.

3. Swapping lo and hi for a 2. Only swap mid with hi (not lo) when nums[mid] == 2. Swapping lo and hi would move elements to the wrong partition.

4. Not swapping in-place. The problem requires O(1) space. Counting and overwriting (two-pass approach) is correct but fails the single-pass follow-up that interviewers almost always ask.

5. Using lo++; mid++ when nums[mid] == 0 and forgetting that lo <= mid. When nums[mid] == 0 and lo < mid, the element at nums[lo] must be 1 (it is in the 1-zone). After the swap, nums[mid] becomes 1, which is in the right zone — advance mid safely.

Solutions#

Python#

def sortColors(nums: list[int]) -> None:
    """
    Modify nums in-place.
    Invariants: nums[0..lo-1] = 0, nums[lo..mid-1] = 1, nums[hi+1..n-1] = 2.
    """
    lo = 0               # left boundary of the 1-zone
    mid = 0              # current inspection pointer
    hi = len(nums) - 1   # right boundary of the 1-zone / unknown region
 
    while mid <= hi:     # process all elements in the unknown region
        if nums[mid] == 0:
            # Move 0 to the 0-zone by swapping with lo
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1      # 0-zone expanded left
            mid += 1     # the element now at mid was already in the 1-zone → safe to advance
        elif nums[mid] == 2:
            # Move 2 to the 2-zone by swapping with hi
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1      # 2-zone expanded right
            # Do NOT advance mid — the element swapped from hi is unknown
        else:
            # nums[mid] == 1 — already in the right zone
            mid += 1

JavaScript#

function sortColors(nums) {
    let lo = 0;                     // next position for a 0
    let mid = 0;                    // current inspection pointer
    let hi = nums.length - 1;       // next position for a 2 (from the right)
 
    while (mid <= hi) {             // unknown region is [mid, hi]
        if (nums[mid] === 0) {
            // Swap 0 into the 0-zone
            [nums[lo], nums[mid]] = [nums[mid], nums[lo]];
            lo++;
            mid++;                  // element at mid was a 1 (from 1-zone), safe to advance
        } else if (nums[mid] === 2) {
            // Swap 2 into the 2-zone
            [nums[mid], nums[hi]] = [nums[hi], nums[mid]];
            hi--;
            // Do NOT advance mid — swapped element from hi is still unknown
        } else {
            mid++;                  // nums[mid] === 1: already in the right zone
        }
    }
}

Complexity Analysis#

The Dutch National Flag algorithm visits each element at most twice (once when mid reaches it, once when it might be swapped). Both mid and hi move monotonically (mid forward, hi backward), so the loop runs at most n iterations. Total: O(n) time, O(1) space, single pass.

Follow-up Questions#

1. Can you do it in one pass without extra space? Yes — that is exactly the Dutch National Flag algorithm above. One pass, O(1) space.

2. What if there are four colors? Use four pointers (lo1, lo2, mid, hi) and maintain four invariants. This generalizes but adds complexity — typically handled with a two-pass approach in practice.

3. How does this relate to quicksort? Three-way partition (Dutch National Flag) is the partition step in three-way quicksort, which handles arrays with many equal elements in O(n log n) average time even when elements are all the same value — unlike standard two-way partition.

4. What if the array is very large and elements only come from {0, 1, 2}? The count-and-overwrite approach avoids swaps entirely, which can be faster in practice due to cache locality. The Dutch National Flag is better when you want a single pass and minimal writes.

This Pattern Solves#

• LC 75 — Sort Colors / Dutch National Flag (this problem)
• LC 283 — Move Zeroes (two-pointer in-place partition)
• LC 27 — Remove Element (two-pointer in-place filtering)
• LC 905 — Sort Array by Parity (partition into even/odd)
• LC 912 — Sort an Array (three-way partition as quicksort subroutine)

Key Takeaways#

• LC 75 is the Dutch National Flag algorithm: maintain three pointers lo, mid, hi and three invariants: [0..lo) = zeros, [lo..mid) = ones, (hi..n-1] = twos.
• When nums[mid] == 0: swap with lo, then advance both lo and mid — the swapped element is known (it was in the 1-zone).
• When nums[mid] == 2: swap with hi, decrement hi, but do NOT advance mid — the swapped-in element from hi is unknown and must be re-inspected.
• When nums[mid] == 1: simply advance mid — it is already in the correct zone.
• Loop condition is mid <= hi (not mid < hi) — the element at mid == hi is still in the unknown region.
• Time O(n), space O(1), single pass — this is the optimal solution and the answer to every "follow-up" the interviewer will ask.
• Microsoft and Facebook use this to test whether candidates can reason about three-region pointer invariants and explain the asymmetric advancement rule for 2s.