Sort Colors: The Dutch National Flag in One Pass

"Sort Colors" is a Medium-level staple in Microsoft, Meta, Amazon loops, and it is a textbook fit for the Two Pointers pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 9 of 12 in the Two Pointers arc.

The Problem

Given an array nums with values 0, 1, and 2 (red, white, blue), sort it in place so same colors are adjacent in that order. The library sort is banned; the follow-up demands a single pass with constant space — Dijkstra's Dutch National Flag.

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

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Three distinct values and an in-place, one-pass demand is the Dutch National Flag signature — a three-pointer partition. Counting sort (two passes) is the warm-up answer; the flag algorithm is the real ask.

The Approach

Maintain three regions via low, mid, high: everything below low is 0, between low and mid is 1, above high is 2, and mid..high is unexplored. Look at nums[mid]: a 0 swaps down to low (both advance), a 1 just advances mid, a 2 swaps up to high (only high retreats — the swapped-in value is unexamined).

That last parenthetical is the classic bug: advancing mid after swapping with high skips inspection of an unknown element. Interviewers watch for exactly this.

Python Solution

def sort_colors(nums: list[int]) -> None:
    """Dutch National Flag: in-place one-pass sort of 0s, 1s, 2s."""
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1  # note: mid stays — new nums[mid] is unexamined

Complexity

• Time: O(n) — mid advances or high retreats every iteration
• Space: O(1) — three indices, swaps in place

Interview Tips and Follow-Ups

• Offer counting sort first (count 0s/1s/2s, rewrite) and label it two-pass — then deliver the one-pass flag. The ladder is the answer.
• Why does mid not advance on the 2-swap? If you cannot answer instantly, re-derive the regions.
• Generalization: partition around a pivot value — this is the partition step inside quicksort's 3-way variant.

If this clicked, continue the Two Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.