Skip to content

Volume ITechnology

4.0.20 — Sort 0s, 1s and 2s: the Dutch National Flag ​

Classic · Medium · LeetCode 75 (Sort Colors)

The problem ​

An array holds only the values 0, 1 and 2. Sort it in place, in one pass, without a sorting function.

[2, 0, 2, 1, 1, 0]  →  [0, 0, 1, 1, 2, 2]

LeetCode calls the values red, white and blue. That is a nod to where the problem comes from. In 1976 the Dutch computer scientist Edsger Dijkstra published it as the Dutch national flag problem, because the flag of the Netherlands has three horizontal stripes: red, white and blue. You have a row of balls in those three colours, mixed up, and must arrange them into the three stripes.

What this problem is really asking ​

Split an array into three groups in one pass, using only swaps. The two-group version of this is the heart of quicksort (4.0.28). The three-group version is what makes quicksort fast on arrays with many repeated values.

Way 1 — Count, then overwrite ​

Count how many 0s, 1s and 2s there are. Then write that many 0s, then 1s, then 2s.

python
def sort_colors_count(nums: list[int]) -> None:
    counts = [0, 0, 0]
    for x in nums:
        counts[x] += 1              # (1)
    i = 0
    for value in range(3):
        for _ in range(counts[value]):
            nums[i] = value         # (2)
            i += 1

a = [2, 0, 2, 1, 1, 0]
sort_colors_count(a)
print(a)   # → [0, 0, 1, 1, 2, 2]

(1) The value itself is the position in counts. This is a tiny counting sort, which 4.0.30 builds out fully.

(2) Rewrite the array from the counts.

This is O(n) and correct. It is a fine first answer. But it takes two passes, and it only works because the elements are plain numbers. Imagine each item is an order with a priority of 0, 1 or 2. Rewriting from the counts would keep the priorities but lose the orders themselves. The interviewer will ask for one pass that moves the real elements.

Way 2 — One pass, three pointers ​

The picture to keep in your head ​

Keep three indexes, low, mid and high. They split the array into four regions.

all 0sall 1snot looked at yetall 2s↑ low↑ midhigh ↑index 0index n − 1
The four regions. Everything before low is 0. From low up to (not including) mid is 1. From mid to high is still unknown. Everything after high is 2. Each step looks at nums[mid] and shrinks the unknown region by one.

At the start, the whole array is unknown. So low = mid = 0 and high = n - 1. Each step looks at nums[mid], the first unknown element, and moves it into the right region. When the unknown region is empty, the array is sorted.

The three cases ​

  1. It is a 0. It belongs at the end of the 0s region. Swap it with nums[low]. Then move low and mid forward by one.
  2. It is a 1. It is already in the right place, at the end of the 1s region. Just move mid forward.
  3. It is a 2. It belongs at the front of the 2s region. Swap it with nums[high]. Then move high back by one. Do not move mid.
python
def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:                                   # (1)
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]  # (2)
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1                                     # (3)
        else:
            nums[mid], nums[high] = nums[high], nums[mid]   # (4)
            high -= 1                                    # (5)

a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a)   # → [0, 0, 1, 1, 2, 2]

b = [2, 2, 0]
sort_colors(b)
print(b)   # → [0, 2, 2]

(1) The unknown region runs from mid to high, both included. <= matters. With <, the last unknown element would never be looked at. Try [1, 0] with <: the loop stops with the 0 still unchecked.

(2) Swap the 0 to the end of the 0s region. What comes back to mid? It came from nums[low]. That position is the first slot of the 1s region, so it holds a 1. The only exception is when low equals mid, and then the element swaps with itself. Either way, the element now at mid is already handled. So mid can move on.

(3) A 1 is already in place. Growing the 1s region is just moving mid.

(4) Swap the 2 to the front of the 2s region.

(5) Here is the one subtle line. The element that came back from high has never been looked at. It is from the unknown region. It might be a 0, a 1 or a 2. So mid must stay where it is, and the next loop step will check it. Moving mid here is the most common bug on this problem.

Trace ​

On [2, 0, 2, 1, 1, 0]:

lowmidhighnums[mid]actionarray after
0052swap with high0 0 2 1 1 2
0040swap with low (itself)0 0 2 1 1 2
1140swap with low (itself)0 0 2 1 1 2
2242swap with high0 0 1 1 2 2
2231move on0 0 1 1 2 2
2331move on0 0 1 1 2 2
243—mid > high, stop0 0 1 1 2 2

Look at row 1. A 2 was swapped away, and a 0 came back from the end. Because mid did not move, the next row checked that 0 and sent it to the front. If mid had moved on, that 0 would have been stranded in the middle.

Why it always finishes, and finishes sorted ​

It finishes. Every step either moves mid forward or moves high back. So the gap between them shrinks by one every step. After at most n steps, mid passes high and the loop ends.

It is sorted when it finishes. The four-region picture is true before the first step, when everything is unknown. Each of the three cases keeps it true. So when the unknown region is empty, only the 0s, 1s and 2s regions are left, in that order. That is a sorted array. This style of argument has a name. A fact that stays true at every step of a loop is called a loop invariant. Here, the invariant is the four-region picture.

Is it stable? ​

No. Stable means equal elements keep their original order. Swapping a 2 from the front to the back jumps it over other elements, including other 2s. For plain numbers, nobody can tell. For records, where two "priority 2" orders differ in other ways, their order can change. The counting version does not have that problem only because it ignores the records altogether.

Complexity ​

One pass. Each step does at most one swap and shrinks the unknown region by one. So it is O(n) time with at most n swaps, and O(1) extra memory.

Variations you will meet ​

  • Two values only, like "move all negatives before positives" or "even before odd". Use two pointers, low and mid, with no high. It is the same partition step that quicksort uses.
  • Partition around a pivot value: everything less than p, then equal to p, then greater. Swap "0" for "less than p", "1" for "equal", "2" for "greater". The code is otherwise the same. This three-way partition is what makes quicksort fast when many values repeat.
  • Four or more values: the three-pointer method does not extend neatly. Use counting.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why don't you move mid after swapping with high?" The number that comes back from high has not been checked yet. It could be 0, 1 or 2. So mid stays put and checks it on the next step.

"Why is it fine to move mid after swapping with low?" The number that comes back from low is always a 1, or the same number. Either way it is already checked.

"Why is the loop mid <= high and not mid < high?" The number at high itself has not been checked yet. With <, the last unchecked number would be skipped.

"Can you do it in one pass?" Counting needs two passes. The three-pointer method does it in one.

"Is it stable?" No. Swapping a 2 to the back can jump it over other equal values.

One thing to volunteer: "This is the three-way split that keeps quicksort fast when the list has many repeated values."

Next: 4.0.21 Majority Element. Finding the value that fills more than half an array, with a voting trick that uses no extra memory.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet