Dutch national flag partition

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The array 2, 0, 2, 1, 1, 0 holds only the values 0, 1 and 2, and you must sort it in place, in one pass. By hand the easy way is to count: two 0s, two 1s, two 2s, then overwrite the array as 0, 0, 1, 1, 2, 2. That is two passes and it works only because the values are tiny labels; it does not generalise to "put everything smaller than a pivot on the left", where you cannot just rewrite the values.

So the real question is: how do you arrange three categories in one sweep, swapping elements rather than counting them?

Build the structure, one piece at a time

Picture the array as four zones, left to right: the 0s, the 1s, the unknown, and the 2s. Three indices mark the borders: lo is the first slot after the 0s, mid is the first unknown slot, hi is the last unknown slot. At the start everything is unknown: lo = mid = 0 and hi = n − 1.

Each step looks at the one element at mid and files it:

• It is a 0: swap it with the slot at lo, which pushes it into the 0 zone and brings a 1 (or itself) to mid. Advance both lo and mid.
• It is a 1: it is already in place at the end of the 1 zone. Advance mid.
• It is a 2: swap it with the slot at hi, which pushes it into the 2 zone. Move hi left, but do not advance mid, because the element that just arrived from hi is still unknown.

Why it is correct

The invariant, kept true after every step: slots 0 … lo − 1 are 0s, slots lo … mid − 1 are 1s, slots hi + 1 … n − 1 are 2s, and slots mid … hi are unknown. At the start the three known zones are empty, so it holds. Check each case. A 0 at mid swaps with slot lo; that slot held a 1 if the 1 zone is non-empty (or the 0 itself if it is empty), so after the swap the 0 zone grows by one and the 1 zone shifts right by one, still all 1s. A 1 at mid extends the 1 zone by one. A 2 at mid swaps with slot hi, growing the 2 zone by one, and the unknown zone shrinks from the right. The loop ends when mid passes hi, so the unknown zone is empty and the array is 0s, then 1s, then 2s.

Why it is fast

Every step either advances mid or moves hi left, so the unknown zone, which starts at size n, shrinks by one each time. Hence at most n steps, each with at most one swap:

≤ n comparisons and ≤ n swaps: O(n) time, O(1) space

It is one pass, unlike counting, and it never looks at an element after it has been filed.

How to recognise it in an interview

Cues: "three kinds of values", "sort colours", "put values less than, equal to, and greater than the pivot in order", "one pass, constant space". Two kinds of values is the simpler two-pointer partition; three is this.

Say: "I will keep three zones with low, mid and high pointers and file the element at mid into the right zone with a swap." Sort Colors is the example. Partition Array According to Given Pivot is the same three zones with "less than", "equal to" and "greater than" the pivot, though that problem also asks to keep the relative order inside each zone, which needs a stable variant. Sort Array By Parity is the two-zone cousin.

02The idea in one line

Three regions: lows, unknown, highs; one pass with low/mid/high pointers.

Reach for it when: Sort three categories in place, partition around a pivot.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Sort Colors on [2,0,2,1,1,0]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Three regions: 0s before lo, 2s after hi, unknown between mid and hi
2. lo and mid start at 0, hi at the last index
3. nums[mid] = 2: swap with hi, hi shrinks; mid stays (unknown came in)
4. nums[mid] = 0: swap with lo, both advance
5. nums[mid] = 0: swap with lo, both advance
6. nums[mid] = 2: swap with hi, hi shrinks; mid stays (unknown came in)
7. nums[mid] = 1: already in the middle region, mid advances
8. nums[mid] = 1: already in the middle region, mid advances
9. mid passed hi: no unknowns left, [0,0,1,1,2,2]
10. One pass, three pointers: O(n) time, O(1) space

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Two Pointers: Opposite ends converge, Fix one, two-pointer the rest, Reader / writer pointers, Merge two sorted sequences, Two-sided max walls.