W
← Blog/dsaarraysstrings

Sort Colors [Medium] — Dutch National Flag Algorithm Explained

Sanjeev SharmaSanjeev Sharma
14 min read

Advertisement

Problem Statement

Given an array nums containing only 0, 1, and 2, sort it in-place so that all 0s come first, followed by all 1s, then all 2s.

You must solve it in one pass using only constant extra space.

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

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

Input:  [0]
Output: [0]

Constraints:

  • n == nums.length, 1 <= n <= 300
  • nums[i] is 0, 1, or 2
  • Must be done in-place in one pass with O(1) extra space

Why This Problem Matters

This problem is LeetCode 75 — and it's not just a "sort this array" question. The reason it appears in nearly every major company's interview loop is because it teaches a fundamental algorithmic pattern: three-way partitioning.

Dijkstra's Original Problem

In 1976, Edsger W. Dijkstra — the same computer scientist behind Dijkstra's shortest-path algorithm and the semaphore — introduced the Dutch National Flag problem in his book A Discipline of Programming (Prentice-Hall, 1976). The original metaphor was elegant: imagine a flagpole scattered with pebbles colored red, white, and blue (the colors of the Dutch flag). Arrange the pebbles so that all reds come first, all whites in the middle, and all blues at the end — using only swaps, no extra containers.

What made Dijkstra's solution remarkable was that he didn't just solve the sorting problem; he derived the algorithm from formal invariants — mathematical properties that must hold true before and after each loop iteration. This approach of reasoning from invariants to code is a masterclass in algorithm design that most programmers never encounter.

Why It Appears in Interviews

The problem sits at the intersection of two critical interview skills:

  1. Partition thinking — recognizing that "sort by category" is fundamentally a partition, not a comparison sort
  2. Invariant-based reasoning — maintaining a precise mental model of what each pointer means at every step

Companies like Microsoft, Facebook, and Google use this problem to test whether candidates can think beyond brute force and reason about pointer semantics precisely enough to avoid off-by-one errors under pressure.

Three Approaches

Approach 1: Built-in Sort — O(n log n) / O(1)

The naive approach is to just call a sort function. Since the values are 0, 1, and 2, any comparison sort will work correctly. But this is O(n log n) and completely ignores the structure of the problem — we only have three distinct values. This approach fails the one-pass constraint and demonstrates no understanding of the underlying partition pattern.

nums.sort()  # Works but misses the point entirely

Approach 2: Two-Pass Counting — O(n) / O(1)

A smarter approach: count the occurrences of each value in the first pass, then overwrite the array in the second pass.

def sortColors_twoPass(nums):
    count = [0, 0, 0]
    for n in nums:
        count[n] += 1
    i = 0
    for val in range(3):
        for _ in range(count[val]):
            nums[i] = val
            i += 1

This is O(n) time and O(1) space, and it's perfectly correct. But it requires two passes — one to count, one to write. The constraint asks for one pass. More importantly, this approach only works when the number of distinct values is small and known in advance. It doesn't generalize.

Approach 3: Dutch National Flag — O(n) / O(1) — One Pass

Dijkstra's algorithm sorts the array in a single pass with constant space using three pointers. This is the approach we need, and it's the one worth understanding deeply.

The Dutch National Flag Algorithm

The Mental Model: Four Regions

At any point during the algorithm, the array is conceptually divided into four regions:

[ 0s | 1s | unknown | 2s ]
  ^    ^    ^         ^
  0   low  mid       high  n-1

More precisely:

  • [0 .. low-1] — all elements here are 0 (confirmed)
  • [low .. mid-1] — all elements here are 1 (confirmed)
  • [mid .. high] — unknown, these elements haven't been processed yet
  • [high+1 .. n-1] — all elements here are 2 (confirmed)

The algorithm starts with low = 0, mid = 0, high = n - 1. The entire array is "unknown." As mid sweeps rightward, the unknown region shrinks until mid > high, at which point every element has been classified and placed correctly.

The Three Cases

At each step, we examine nums[mid]:

Case 1: nums[mid] == 0 Swap nums[mid] with nums[low]. Since the region [0..low-1] contained only 0s, and [low..mid-1] contained only 1s, we know that nums[low] is currently a 1 (or 0 if low == mid). After the swap, the element at position mid is now a 1, which is correct for its position. We advance both low and mid.

Case 2: nums[mid] == 1 The element is already in the right region — the 1s zone. Simply advance mid.

Case 3: nums[mid] == 2 Swap nums[mid] with nums[high]. The 2 is now at the end where it belongs, and high shrinks. Do not advance mid. (See the next section for exactly why.)

The Loop Termination Condition

The loop continues while mid <= high. When mid > high, the unknown region is empty — every element has been correctly placed. Note: we do not use mid < n as the condition, because elements in [high+1..n-1] are already confirmed 2s and must not be re-examined.

The Critical Detail: Why We Don't Increment mid After Swapping With high

This is the single most important subtlety in the algorithm, and it's where the majority of candidates introduce a bug.

When nums[mid] == 2, we swap it to position high. Now high decrements. But what came from high into position mid? We have no idea. It could be a 0, a 1, or even another 2. Whatever it is, it's now sitting at mid and has never been examined.

If we naively increment mid here, we would skip over this unexamined element entirely. It would remain in the wrong position, and the array would be incorrectly sorted.

Contrast this with Case 1 (swapping with low): When nums[mid] == 0, we swap with nums[low]. We know that nums[low] is a 1 (because the region [low..mid-1] contains only confirmed 1s). After the swap, position mid holds a 1, which is exactly what should be in the 1s region. So it's safe — in fact, necessary — to advance mid.

The asymmetry is critical:

  • Swapping with low brings in a known value (a 1). Advance mid.
  • Swapping with high brings in an unknown value. Don't advance mid.

Visual Dry Run: [2, 0, 2, 1, 1, 0]

Let's trace the algorithm step by step. Initial state: low=0, mid=0, high=5.

State: [2, 0, 2, 1, 1, 0]
        ^              ^
       mid            high
       low

Step 1: nums[mid=0] = 2. Swap with nums[high=5]. high becomes 4. mid stays 0.

State: [0, 0, 2, 1, 1, 2]
        ^           ^
       mid         high
       low

Step 2: nums[mid=0] = 0. Swap with nums[low=0] (no-op swap). low becomes 1, mid becomes 1.

State: [0, 0, 2, 1, 1, 2]
           ^        ^
          mid      high
          low

Step 3: nums[mid=1] = 0. Swap with nums[low=1] (no-op swap). low becomes 2, mid becomes 2.

State: [0, 0, 2, 1, 1, 2]
              ^     ^
             mid   high
             low

Step 4: nums[mid=2] = 2. Swap with nums[high=4]. high becomes 3. mid stays 2.

State: [0, 0, 1, 1, 2, 2]
              ^  ^
             mid high
             low

Step 5: nums[mid=2] = 1. It's in the right place. mid becomes 3.

State: [0, 0, 1, 1, 2, 2]
                 ^
                mid
                high
                low (=2 still)

Step 6: nums[mid=3] = 1. It's in the right place. mid becomes 4.

Now mid (4) > high (3). Loop ends.

Result: [0, 0, 1, 1, 2, 2] — correct in 6 steps, one pass.

Common Mistakes

Mistake 1: Incrementing mid After Swapping With high

# WRONG
elif nums[mid] == 2:
    nums[mid], nums[high] = nums[high], nums[mid]
    high -= 1
    mid += 1  # Bug! The swapped element is unexamined

This skips the value that just arrived at mid from the high end. On inputs like [2, 2, 0], this produces incorrect output.

Mistake 2: Using mid < n as the Loop Condition

# WRONG
while mid < len(nums):  # Should be mid <= high

After high shrinks, elements in [high+1..n-1] are confirmed 2s. Continuing to iterate into that zone will re-examine — and potentially misplace — those elements.

Mistake 3: Off-by-One in Initial high

# WRONG
high = len(nums)  # Should be len(nums) - 1

This causes an index-out-of-bounds when swapping nums[mid] with nums[high] on the first iteration.

Mistake 4: Not Handling the Case Where low == mid

When low == mid and nums[mid] == 0, swapping nums[low] and nums[mid] is a no-op — you're swapping the element with itself. This is harmless; both pointers still advance correctly. Some candidates add a special case if low != mid: swap(...) which is unnecessary. The algorithm handles it naturally.

Solutions

Python — All Three Approaches

from typing import List

class Solution:
    # ---------------------------------------------------
    # Approach 1: Two-pass counting — O(n) time, O(1) space
    # Correct but uses two passes; fails the one-pass constraint
    # ---------------------------------------------------
    def sortColors_twoPass(self, nums: List[int]) -> None:
        count = [0, 0, 0]
        for n in nums:
            count[n] += 1        # Count occurrences of 0, 1, 2

        i = 0
        for val in range(3):     # Overwrite array with sorted values
            for _ in range(count[val]):
                nums[i] = val
                i += 1

    # ---------------------------------------------------
    # Approach 2: Dutch National Flag — O(n) time, O(1) space
    # One pass. The correct, elegant solution.
    # ---------------------------------------------------
    def sortColors(self, nums: List[int]) -> None:
        low = 0          # next position for 0
        mid = 0          # current element under examination
        high = len(nums) - 1  # next position for 2

        # Invariants:
        #   nums[0..low-1]   == 0  (all 0s confirmed)
        #   nums[low..mid-1] == 1  (all 1s confirmed)
        #   nums[mid..high]  == ?  (unknown region)
        #   nums[high+1..n-1]== 2  (all 2s confirmed)

        while mid <= high:
            if nums[mid] == 0:
                # Bring 0 to the front; the element at low is a 1 (or
                # mid==low in which case it's a no-op). After swap,
                # position mid holds a 1, which is correct. Advance both.
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1

            elif nums[mid] == 2:
                # Send 2 to the back. The element coming from high is
                # UNKNOWN — it could be 0, 1, or 2. Do NOT advance mid;
                # re-examine position mid in the next iteration.
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
                # mid intentionally NOT incremented

            else:
                # nums[mid] == 1: already in the correct region
                mid += 1

JavaScript — All Three Approaches

/**
 * Approach 1: Two-pass counting — O(n) time, O(1) space
 * Counts values first, then rewrites the array. Two passes.
 * @param {number[]} nums
 * @return {void}
 */
function sortColorsTwoPass(nums) {
    const count = [0, 0, 0];
    for (const n of nums) count[n]++;   // Count occurrences

    let i = 0;
    for (let val = 0; val < 3; val++) { // Overwrite with sorted values
        for (let j = 0; j < count[val]; j++) {
            nums[i++] = val;
        }
    }
}

/**
 * Approach 2: Dutch National Flag — O(n) time, O(1) space
 * Single pass. Three-pointer invariant-based algorithm.
 *
 * Regions at any point:
 *   [0 .. low-1]   → confirmed 0s
 *   [low .. mid-1] → confirmed 1s
 *   [mid .. high]  → unknown (shrinks each iteration)
 *   [high+1 .. n-1]→ confirmed 2s
 *
 * @param {number[]} nums
 * @return {void}
 */
var sortColors = function(nums) {
    let low = 0;
    let mid = 0;
    let high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            // 0 belongs at the front. Swap with low boundary.
            // nums[low] is a 1 (or same element if low===mid).
            // After swap, nums[mid] is a 1 → safe to advance mid.
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;

        } else if (nums[mid] === 2) {
            // 2 belongs at the back. Swap with high boundary.
            // What came from high is UNKNOWN — don't advance mid.
            // Only shrink the high boundary.
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
            // mid is NOT incremented — re-examine nums[mid] next iteration

        } else {
            // nums[mid] === 1: already in the correct 1s region
            mid++;
        }
    }
};

Complexity Analysis

ApproachTimeSpacePasses
Built-in sortO(n log n)O(1) or O(n)1 (internally multi)
Two-pass countingO(n)O(1)2
Dutch National FlagO(n)O(1)1

Why exactly O(n)? Each element is examined at most once. When mid advances (Cases 1 and 2b), it never retreats. When high decrements (Case 3), the unknown region shrinks from the right. The total number of operations is bounded by n.

Why O(1) space? Only three integer pointers are maintained regardless of input size. No auxiliary array, no recursion stack.

Follow-up Questions

1. Sort Array by Parity — LC 905

Partition an array so all even numbers come before odd numbers. This is a two-way version of the same pattern — use low and mid only (drop high). A classic two-pointer swap from both ends works.

def sortArrayByParity(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        if nums[l] % 2 == 1 and nums[r] % 2 == 0:
            nums[l], nums[r] = nums[r], nums[l]
        if nums[l] % 2 == 0: l += 1
        if nums[r] % 2 == 1: r -= 1
    return nums

2. Sort Array by Parity II — LC 922

Every even-indexed position must hold an even number; every odd-indexed position must hold an odd number. Still a partition problem, but with positional constraints. Walk two pointers — one through even indices, one through odd indices — swapping when they find misplaced elements.

3. Four-Color Variant (k-way Partition)

What if you have 4 colors instead of 3? The DNF approach generalizes: maintain k-1 boundaries and sweep. For 4 colors, you'd need two sweeps or a more complex multi-pointer scheme. This is the k-way partition problem and appears in external sorting and database query optimization.

4. Partition Array Around a Pivot — LC 2161

Given a pivot value, partition an array so all elements less than pivot come first, then equal elements, then greater elements — without guaranteed O(n log n) sort complexity. This is exactly the Dutch National Flag problem abstracted to arbitrary values.

5. 3-Way Partition in QuickSort

Dijkstra's DNF is the foundation of 3-way QuickSort (also called Dutch-flag QuickSort), which handles arrays with many duplicate elements in O(n) average time instead of degrading to O(n²). This is the algorithm used in Java's Arrays.sort() for primitive types.

This Pattern Solves

The Dutch National Flag pattern — maintaining ordered regions via invariant-preserving pointer movements — applies to any problem that asks you to classify elements into ordered groups in-place:

  • Move Zeroes (LC 283) — 2-way: zeros to the end, non-zeros to the front
  • Remove Duplicates from Sorted Array (LC 26) — 2-way partition
  • Segregate even/odd, negative/positive — 2-way DNF
  • Wiggle Sort (LC 280) — modified 3-way partition
  • Partition Labels (LC 763) — partition by character boundaries
  • QuickSelect / QuickSort pivoting — DNF as the partition step

Whenever you see "rearrange in-place by category," think Dutch National Flag.

Key Takeaway

Dijkstra's Dutch National Flag algorithm is deceptively simple to code but demands precise invariant reasoning — particularly around the asymmetry between swapping with low (advances mid) versus swapping with high (does not advance mid). Once you internalize that asymmetry and the four-region mental model, you can apply this three-pointer pattern to an entire family of partition problems far beyond just sorting 0s, 1s, and 2s.

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro

twitterlinkedingithubmail

← Previous

Insert Interval [Medium] — Sweep and Merge

Next →

Find the Duplicate Number — Floyd's Cycle Detection Fully Explained [Google, Amazon Hard-Medium]