Day 5 of 250: LeetCode 75 Sort Colors | Dutch National Flag Algorithm Explained

What Is This Problem Really Asking?

LeetCode 75, Sort Colors, looks like a sorting problem on the surface. The word "sort" is right there in the title. But the moment you read the constraint that says you cannot use a library sort function, you realize the problem is testing something far more specific.

It is testing whether you can maintain multiple invariants simultaneously as you scan an array in a single pass. That is a completely different skill from general sorting, and it is exactly the kind of thinking that senior engineers demonstrate in technical interviews.

Let us get into it.

Problem Statement

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, blue. You must solve this problem without using the library sort function.
We use the integers 0 for red, 1 for white, and 2 for blue.

Examples:

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]

Constraints:

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

The Core Insight: You Already Know Where Every Element Belongs

Here is the observation that unlocks the entire solution.

In a general sorting problem, you do not know where any element belongs until you have compared it against other elements. That is why general sorting costs O(n log n). Comparisons are expensive.

But in this problem, values can only be 0, 1, or 2. You know exactly where every element belongs before you even look at it. A 0 belongs at the front. A 2 belongs at the back. A 1 belongs in the middle.

You do not need to compare elements against each other at all. You need to route each element to its correct region.

Think of it as a mail sorting machine with three fixed bins labeled LEFT, CENTER, and RIGHT. Every letter is already labeled 0, 1, or 2. You pick it up and drop it into the right bin. You never compare two letters against each other. You just route each one to where it belongs.

That routing insight is what makes a single-pass O(n) solution possible. The constraint that seemed like a handicap, only three possible values, is actually the key that unlocks a far more efficient algorithm than any general sort.

First Instincts vs Correct Thinking

A beginner looking at this problem will almost always jump to one of two approaches, and both fall short in an interview setting.

The first instinct is to count. Count all the 0s, count all the 1s, count all the 2s, then overwrite the array in order. This does work and it gives you O(n) time, but it requires two passes and an extra count array. The moment your interviewer asks "can you do this in a single pass with O(1) space?", this approach has no answer.

The second instinct is to use a simple two-pointer swap, like the partition step in quicksort, to push 0s to the left and 2s to the right. This handles two groups reasonably well, but when you try to extend it to three groups simultaneously, the pointer logic breaks down. You end up with overlapping regions and no clean way to track what has been processed and what has not.

The mental shift you need is this: instead of thinking about moving elements to their destination one group at a time, think about maintaining three confirmed regions at once while a scanner moves through the unconfirmed middle. Every iteration of the scanner either confirms an element into a region or routes it somewhere it belongs. The unconfirmed zone shrinks by at least one on every step.

Once you frame it that way, three pointers feel completely natural. This approach is known as the Dutch National Flag algorithm, named by computer scientist Edsger Dijkstra after the three colored bands of the Dutch flag.

Understanding the Approach

We use three pointers and we need to be precise about what each one means, because every swap and movement decision flows directly from these definitions.

low marks the right boundary of the confirmed 0 region. Everything to the left of low is a confirmed 0.

mid is our scanner. It points to the element currently being evaluated. Everything between low (inclusive) and mid (exclusive) is a confirmed 1.

high marks the left boundary of the confirmed 2 region. Everything to the right of high is a confirmed 2.

The region from mid to high (inclusive) is the unprocessed zone. We loop until mid exceeds high, which means the unprocessed zone has been completely eliminated.

The movement rules in plain English:

When nums[mid] is 0: it belongs at the front, so swap it with nums[low]. Move both low and mid forward. We advance mid here because the value that came from low was previously in the confirmed 1 zone, so it is a 1 and already in the right place.

When nums[mid] is 1: it is already in the right region. Just move mid forward.

When nums[mid] is 2: it belongs at the back, so swap it with nums[high]. Move high backward. We do NOT advance mid here, because the element that arrived from high came from the unprocessed zone and has never been evaluated.

That last point is the critical asymmetry. It is the thing that makes the algorithm provably correct and the thing that trips up most people who try to implement it from memory.

Deep Dry Run: Every Step Explained

We trace through Example 1 completely, one iteration at a time.

Input:  [2, 0, 2, 1, 1, 0]
Index:   0  1  2  3  4  5

Initial state:
low  = 0
mid  = 0
high = 5

Iteration 1

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

nums[mid] = 2
Condition: nums[mid] === 2
Action: swap nums[mid] with nums[high], then high--

After: [0,  0,  2,  1,  1,  2]
low  = 0
mid  = 0   (stays — the swapped-in element is unprocessed)
high = 4

The 2 from index 0 went to its confirmed right region. The 0 that swapped in from index 5 has never been evaluated, so mid must stay put.

Iteration 2

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

nums[mid] = 0
Condition: nums[mid] === 0
Action: swap nums[mid] with nums[low], then low++, mid++

After: [0,  0,  2,  1,  1,  2]   (no visible change — low == mid)
low  = 1
mid  = 1
high = 4

The 0 at index 0 is confirmed. The swap is a no-op here because low and mid point to the same index, but advancing both pointers is still correct and necessary.

Iteration 3

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

nums[mid] = 0
Condition: nums[mid] === 0
Action: swap nums[mid] with nums[low], then low++, mid++

After: [0,  0,  2,  1,  1,  2]   (no visible change — low == mid again)
low  = 2
mid  = 2
high = 4

Another 0 confirmed. Both pointers advance together.

Iteration 4

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

nums[mid] = 2
Condition: nums[mid] === 2
Action: swap nums[mid] with nums[high], then high--

After: [0,  0,  1,  1,  2,  2]
low  = 2
mid  = 2   (stays — swapped-in element is unprocessed)
high = 3

The 2 at index 2 is placed in the confirmed right region. The 1 that came from index 4 is now at index 2 and must be evaluated.

Iteration 5

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

nums[mid] = 1
Condition: nums[mid] === 1
Action: mid++

After: no swap
mid  = 3

A 1 is already in the correct region. The scanner just moves forward.

Iteration 6

[0,  0,  1,  1,  2,  2]
              ^
             mid
              ^
             high
low = 2

nums[mid] = 1
Condition: nums[mid] === 1
Action: mid++

After: no swap
mid  = 4

mid (4) > high (3) — the loop condition fails. We stop.

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

Bonus Trace: Example 2

Input: [2, 0, 1]
low=0, mid=0, high=2

Step 1: nums[0]=2, swap with high → [1, 0, 2], high=1, mid stays at 0
Step 2: nums[0]=1, mid++ → mid=1
Step 3: nums[1]=0, swap with low → [0, 1, 2], low=1, mid=2
mid(2) > high(1), stop.

Output: [0, 1, 2]

What Made It Work: The Deeper Why

1. The invariants hold after every single operation, not just at the end.

Before any step, everything before low is a 0, everything between low and mid is a 1, and everything after high is a 2. After every swap and pointer movement, you can verify the same statement is still true. An algorithm that preserves true invariants across all operations cannot produce a wrong answer. This is the formal basis for why the algorithm is correct, beyond intuition.

2. Not advancing mid after a high swap is mathematically necessary.

When we swap nums[mid] with nums[high], the value that lands at mid came from the unprocessed zone. It has never been evaluated. Moving mid forward without evaluating it would skip an element, potentially leaving a 0 or 2 stranded in the 1 region. The algorithm is only correct because we treat every swap-in from the right as a brand new, unclassified element.

3. Advancing both low and mid after a low swap is provably safe.

When we swap nums[mid] with nums[low], the value that arrives at mid came from the confirmed 1 region (everything between low and mid was known to be a 1). So the element sitting at mid after the swap is already a confirmed 1. Re-evaluating it would be a wasted step. Advancing mid immediately is not just allowed, it is required for O(n) performance.

4. The algorithm terminates in at most n steps.

Every iteration either advances mid or decreases high. The gap between mid and high starts at n and shrinks by at least 1 per iteration. The loop terminates in at most n iterations, guaranteeing linear time regardless of the input arrangement.

The Code

var sortColors = function(nums) {
    let low = 0, mid = 0, high = nums.length - 1;

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

We initialize low and mid at index 0, and high at the last index. These are the three boundary markers for our three confirmed regions.

The while (mid <= high) condition keeps the loop running as long as there is at least one unprocessed element. The moment mid exceeds high, the unconfirmed zone has collapsed to nothing and every element is classified.

When nums[mid] is 0, we swap it into the confirmed 0 zone at index low. Both low and mid advance because the value that moved to position mid was previously a confirmed 1 and requires no re-evaluation.

When nums[mid] is 1, no swap is needed. The element is already in its correct region. We advance mid alone to evaluate the next unclassified element.

When nums[mid] is 2, we swap it with the element at high, placing the 2 into the confirmed right region. We decrement high to shrink the right boundary inward. We deliberately do not advance mid because the element that swapped into position mid is fresh from the unclassified zone and needs to be evaluated on the next iteration.

Complexity Analysis

Common Mistakes

Mistake 1: Advancing mid after swapping with high

// WRONG
} else {
    [nums[mid], nums[high]] = [nums[high], nums[mid]];
    high--;
    mid++; // do not do this
}

This skips evaluating the element that just swapped in from the unprocessed right region. It can silently leave a 0 or 2 stranded inside the middle region, producing a wrong output with no error thrown.

Mistake 2: Using mid < high instead of mid <= high as the loop condition

// WRONG
while (mid < high) { ... }

This exits one iteration too early and skips the last unprocessed element. If that final element is a 2 or a 0 out of place, the output will be wrong.

Mistake 3: Reaching for the two-pass counting solution when one pass is expected

// Works but will not satisfy the follow-up
const count = [0, 0, 0];
for (let n of nums) count[n]++;
let i = 0;
for (let val = 0; val < 3; val++)
    while (count[val]-- > 0) nums[i++] = val;

This is a valid two-pass O(n) solution, but it uses O(1) extra space only if you do not count the count array, and it cannot answer the follow-up question about doing it in a single pass. In an interview, knowing this approach but not the Dutch National Flag algorithm leaves you stuck.

Mistake 4: Treating low and mid as permanently linked

Some implementations assume low and mid always move together. They do not. After swapping a 2 to the right and receiving an unknown element back, mid stays while high moves. The two pointers decouple precisely when they need to, and that flexibility is what makes the algorithm work.

Mistake 5: Swapping based on value comparisons between elements

Thinking of this as a sort leads you to compare nums[i] against nums[j] to decide which goes first. But since you already know each value's destination before looking at it, comparisons are completely unnecessary. Treating it as a sort adds O(n log n) complexity to a problem that has an O(n) solution.

Interview Tips

1. Open by naming what the problem really is. Say out loud: "This looks like sorting, but it is actually a three-way partition. There are only three possible values and each one has a fixed destination, so I do not need to compare elements against each other at all." This signals that you have identified the structure of the problem, not just its surface.
2. State your invariants before touching the code. Tell the interviewer exactly what each pointer represents and what the array guarantees hold at every moment. Invariant-first thinking is one of the clearest signals of engineering maturity that you can show in a 45-minute interview.
3. Highlight the asymmetry between the two swap cases explicitly. Make it clear that after swapping with low you advance mid, but after swapping with high you do not, and explain exactly why. This is the point where most interviewers will probe, and having a clear answer ready demonstrates genuine understanding rather than memorization.
4. Trace through the example before writing any code. A 60-second verbal trace through [2, 0, 2, 1, 1, 0] shows the interviewer that your mental model is correct before any code appears. It also surfaces edge case bugs before they become debugging sessions.
5. Close by stating complexity and teasing the generalization. Wrap up with "This runs in O(n) time and O(1) space, single pass, fully in-place." Then add: "If the problem extended to k colors instead of 3, I would look at how to generalize the partition boundaries." That shows you are already thinking one level beyond the problem in front of you.

Key Takeaways

This is a partitioning problem, not a sorting problem. The moment you recognize that every element has a fixed known destination, comparisons between elements become unnecessary and a one-pass solution becomes achievable.

Invariants are the backbone of pointer algorithms. The correctness of the Dutch National Flag algorithm does not come from the swaps themselves. It comes from the invariants that every swap and pointer movement carefully preserves at each step.

The asymmetry between the two swap cases is the crux of the algorithm. Advancing mid after a low swap is safe because the arriving value is a known 1. Not advancing mid after a high swap is mandatory because the arriving value is unknown and unprocessed.

The Dutch National Flag algorithm is a must-know interview pattern. It appears in its pure form in Sort Colors and in modified form across quicksort partitioning, wiggle sort, and k-way partition problems. Understanding it deeply means you can adapt it whenever a "divide into fixed regions in one pass" structure appears.

Day 5 is done. We took a problem that looks like sorting, recognized it as partitioning, and applied the Dutch National Flag algorithm to solve it in a single pass with constant space.

Day 6 is up next. If you have questions about today's logic, especially around why mid does not advance after swapping with high, drop them in the comments. The best way to lock this in is to trace through edge cases yourself: try an all-zeros array, an all-twos array, and a single-element array and watch how the three pointers behave.

See you on Day 6. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.