The problem. An array nums holds only the values 0, 1 and 2 — think of them as red, white and blue. Sort it in place so all 0s come first, then all 1s, then all 2s. You may not use a library sort, and the follow-up asks for a single pass.
![Before: [2, 0, 2, 1, 1, 0] as blue, red, blue, white, white, red. After: [0, 0, 1, 1, 2, 2] as two reds, two whites, two blues.](/drawings/b04031fd-ef5a-498f-b2ec-68da5df132c7.svg)
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Input: nums = [2, 0, 1]
Output: [0, 1, 2]This is a sort with a twist: there are only three possible values. The puzzle is famous as the Dutch national flag problem (the Dutch flag is three stripes), posed by Edsger Dijkstra.
Free account
Sign up to read the rest of this lesson: 5 more sections, 3 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.
Still to come