cf.completefrontend
TWO POINTERS · CORE

Dutch national flag (three-way partition)

Sort a list that holds only three kinds of values in one pass by swapping each item into a low, middle, or high zone.

Time O(n)Space O(1)4 practice problemsStep-through picture

The idea

Some lists hold only three kinds of values: 0, 1, and 2, or low, medium, and high. You could count each kind and rewrite the list, but that takes two passes. The Dutch national flag method, named after a flag with three stripes, sorts the list in one pass and in place.

It keeps three indexes. Everything before low is a 0. Everything after high is a 2. Everything from low up to just before mid is a 1. The items from mid to high haven't been looked at yet. Each step looks at nums[mid] and swaps it into the right zone.

A 0 swaps to the low side and both low and mid move right. A 1 is already in the middle zone, so only mid moves. A 2 swaps to the high side and high moves left, but mid stays, because the item that came back from the end hasn't been looked at yet.

An everyday example

Sorting laundry into three piles on one shelf

You have one long shelf of folded clothes: whites, colors, and darks, all mixed. You push whites to the left end, darks to the right end, and colors stay in the middle. You check clothes one by one from the left. A white swaps into the next white spot. A color stays where it is. A dark swaps with whatever sits at the right end of the unchecked part, and since you haven't checked that item yet, you look at it next.

How the example maps to the code
In the exampleIn the code
The next spot for a white itemlow
The item you are checkingnums[mid]
The next spot for a dark itemhigh
Swapping a white item to the left zone[nums[low], nums[mid]] = [nums[mid], nums[low]]
Swapping a dark item to the right zone[nums[mid], nums[high]] = [nums[high], nums[mid]]

From the slow way to dutch national flag (three-way partition)

  1. Start with a general sort: nums.sort((a, b) => a - b). It works, but it costs O(n log n) and ignores that there are only three different values. Knowing the values in advance should make this easier.
  2. Counting is the next idea: count the 0s, 1s, and 2s in one pass, then write that many of each in a second pass. That is O(n), but it needs two passes, and it only works when the items are the values themselves. If each item is an object with a priority field, you can't rebuild the objects from three counts.
  3. So move the real items instead. A read and write sweep can push all 0s to the front in one pass. Do that from both ends at once: 0s are swapped toward the front, 2s toward the back, and the 1s are left in between, where they belong.
  4. That needs three boundaries: low for the next 0 slot, high for the next 2 slot, and mid for the item being checked. Each step looks at nums[mid] and either swaps it to one end or leaves it. That loop is the Dutch national flag partition.

How it works

  1. Set low = 0, mid = 0, and high to the last index.
  2. While mid <= high, look at nums[mid].
  3. If it's 0, swap nums[low] and nums[mid], then move both low and mid one step right.
  4. If it's 1, it's already in the middle zone: move mid one step right.
  5. If it's 2, swap nums[mid] and nums[high], then move high one step left. Don't move mid: the item that just arrived is unchecked.
  6. When mid passes high, every item is in its zone and the list is sorted.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function sortThree(nums) {
  2. let low = 0;
  3. let mid = 0;
  4. let high = nums.length - 1;
  5. while (mid <= high) {
  6. if (nums[mid] === 0) {
  7. [nums[low], nums[mid]] = [nums[mid], nums[low]];
  8. low++;
  9. mid++;
  10. } else if (nums[mid] === 1) {
  11. mid++;
  12. } else {
  13. [nums[mid], nums[high]] = [nums[high], nums[mid]];
  14. high--;
  15. }
  16. }
  17. return nums;
  18. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each step shrinks the unchecked zone by one, so there are n steps with at most one swap each. It only stores three indexes.

  • Best caseO(n)

    All 1s, like [1, 1, 1, 1]: no swaps, just n steps of mid++.

  • Average caseO(n)

    Any mix: exactly n steps, each with at most one swap.

  • Worst caseO(n)

    Still n steps. The most swaps happen when there are no 1s at all, like [2, 2, 2, 2], where every step is a swap, some of an item with itself.

Common mistakes

  • Moving mid forward after swapping a 2 to the end. The item that came back is never checked, and a 0 can end up stuck in the middle.
  • Looping with mid < high. The last unchecked item is skipped when mid equals high.
  • Using it for more than three kinds of values. With four kinds, the zones don't cover every case; run a partition twice or count instead.
  • Expecting equal items to keep their original order. The swaps move items around, so this sort is not stable; don't use it when items with the same key must stay in order.

When to use it

Look for these clues in a problem:

  • The values come in exactly three kinds, such as 0, 1, 2 or "less than, equal to, more than" a pivot.
  • The list must be sorted or grouped in place with O(1) extra memory.
  • The question asks for one pass, so counting first and rewriting later is not allowed.
  • You are writing a quick sort that handles many repeated values.

Check yourself

Answer each one in your head first, then open it.

Why does mid move after swapping a 0 but not after swapping a 2?

The item that comes from low is a 1 from the middle zone (or the same 0), so it's already checked. The item that comes from high is unchecked and could be anything.

Why is the condition mid <= high and not mid < high?

When mid === high, one unchecked item remains. With <, it would be skipped, and a 0 there would stay in the wrong place.

How many loop steps does a list of 10 items take?

Exactly 10. Each step shrinks the unchecked zone by one item, and it starts with all 10.

Is this sort stable?

No. A 2 swapped to the end can jump over other 2s, so equal items can change order.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps four zones true at every step: indexes 0 to low - 1 hold 0s, low to mid - 1 hold 1s, mid to high are unchecked, and high + 1 to the end hold 2s. At the start, low and mid are 0 and high is the last index, so the first, second, and fourth zones are empty and everything is unchecked.

Each case keeps the zones. A 0 at mid swaps with nums[low], which is the first 1 (or the same item when the 1 zone is empty), so after low++ and mid++ both zones are still right. A 1 just joins the 1 zone with mid++. A 2 swaps with nums[high] and high-- grows the 2 zone; the item that came back is unchecked, which is exactly why mid stays.

Every step shrinks the unchecked zone by one: either mid moves right or high moves left. It starts with n items, so the loop runs exactly n times. When it ends, the unchecked zone is empty, and the other three zones cover the whole list in order: all 0s, then 1s, then 2s.

Going deeper

3 more ideas

The four zones the loop keeps

At every step: indexes 0 to low - 1 hold 0s, indexes low to mid - 1 hold 1s, indexes mid to high are not checked yet, and indexes high + 1 to the end hold 2s. Each case of the loop shrinks the unchecked zone by one and keeps the other three zones correct. When the unchecked zone is empty, the list is sorted.

Why mid moves after a 0 swap but not after a 2 swap

When nums[mid] is 0, it swaps with nums[low]. That item came from the 1 zone (or is the same item), so it is a known 1 and mid can move on. When nums[mid] is 2, it swaps with nums[high], which came from the unchecked zone. It could be a 0, 1, or 2, so mid must look at it before moving.

Why it takes O(n) time

Every step either moves mid right or moves high left, so the unchecked zone shrinks by one item per step. It starts with n items, so there are exactly n steps, each with at most one swap. The three indexes are the only extra memory.

Work it by hand

Every step in a table, with why

Sort 7 items. A 2 swapped from the end brings back a 1, and a later 2 brings back a 0, so mid has to stay put twice.

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

Steplowmidhighnums[mid]nums afterWhat happensWhy
10061[1, 2, 0, 1, 2, 0, 1]A 1: mid++A 1 already belongs in the middle zone, so only mid moves.
20162[1, 1, 0, 1, 2, 0, 2]A 2: swap with nums[6], high--The 2 goes to the end. A 1 comes back from index 6, unchecked, so mid stays at 1.
30151[1, 1, 0, 1, 2, 0, 2]A 1: mid++The item that came back is a 1, so now mid can move on.
40250[0, 1, 1, 1, 2, 0, 2]A 0: swap with nums[0], both moveThe 0 swaps with the first 1. The 1 it gets back is a known 1, so low and mid both move.
51351[0, 1, 1, 1, 2, 0, 2]A 1: mid++Three 1s now sit together in the middle zone.
61452[0, 1, 1, 1, 0, 2, 2]A 2: swap with nums[5], high--This time a 0 comes back from the end. mid stays to check it.
71440[0, 0, 1, 1, 1, 2, 2]A 0: swap with nums[1], both moveThe 0 goes to index 1 and a 1 moves to index 4. Now mid is 5 and high is 4.

It returns [0, 0, 1, 1, 1, 2, 2] after 7 steps, one per item. The loop stops because mid (5) has passed high (4): no unchecked items remain.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Dutch national flag (three-way partition)O(n)O(1)There are exactly three kinds, the items must move in place, and one pass is required.
Counting sortO(n)O(1)The items are plain values, two passes are fine, and you want the simplest code.
Built-in sort with a compare functionO(n log n)O(n)The list is small, or equal items must keep their order: JavaScript's sort is stable.

Extra memory: O(1): three indexes. The swaps happen inside nums.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Dutch national flag (three-way partition) and the other approaches, on a scale where each line up is 10 times more steps.
  • Dutch national flag (three-way partition), Counting sort O(n)
  • Built-in sort with a compare function O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Dutch national flag (three-way partition)101,0001 million
Counting sort101,0001 million
Built-in sort with a compare function339,96620 million

Inputs that need care

5 tricky inputs
An empty list: nums = []
high starts at -1, so mid <= high is false and the empty list is returned as it is.
All 2s: nums = [2, 2, 2, 2]
Every step swaps nums[mid] with nums[high] and moves high left while mid stays at 0. The last swap is index 0 with itself. Four swaps, and the list is unchanged, which is correct.
All 0s: nums = [0, 0, 0]
Each 0 swaps with itself, because low === mid the whole time. Three harmless swaps.
A value other than 0, 1, or 2: nums = [1, 3, 0, -1, 2]
The else branch treats anything that isn't 0 or 1 as a 2, so 3 and even -1 go to the high zone: the result is [0, 1, -1, 2, 3]. Validate the input, or compare with a pivot instead.
Objects with equal keys that must keep their order
Swaps move items across long distances, so two items with the same key can change order. This partition isn't stable; use a stable sort or three separate lists if the order matters.

Variations and follow-ups

Twists interviewers add

Partition around a pivot

Replace the tests with nums[mid] < pivot, nums[mid] === pivot, and nums[mid] > pivot. This three-way partition is how quick sort stays fast on lists with many repeated values: all items equal to the pivot are finished in one pass.

Counting sort

When items are just the values 0, 1, 2, counting each value and rewriting the list is also O(n) and very simple. It takes two passes and can't move objects that carry other data.

Two-way partition

With only two kinds of values, such as even and odd, one boundary is enough: a read and write sweep, or two pointers from opposite ends that swap a misplaced pair.

More than three kinds

For four kinds, run a two-way partition to split {0, 1} from {2, 3}, then partition each half. Or count, if the values are small integers.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "only three values", "group into low, medium, high", or "sort 0s, 1s, and 2s in one pass and in place".
  • Draw the four zones before coding, and say which index bounds each one. Once the zones are clear, each branch of the loop writes itself.
  • Say why mid doesn't move after the 2 swap: the item that came from high is unchecked. Interviewers often ask exactly this, and it is the most common bug.
  • Expect the follow-up "can you do it with a pivot, for quick sort?". The answer is the same loop with < pivot, === pivot, and > pivot tests.

Where frontend code uses it

The same idea in real UI code
  • Grouping a list of notifications by severity (errors, warnings, info) in place before rendering, when the list is large and memory is tight.
  • Quick sort with three-way partitioning, which splits items into less than, equal to, and greater than a pivot. It stays fast on lists with many repeated values, such as table rows sorted by a status column.
  • Ordering task cards in a board column into blocked, in progress, and done groups with one pass over the array.

Related algorithms