Sort Colors
On this page
Problem statement
An array contains only the values 0, 1 and 2. Sort it in place so that all 0s come first, then all 1s, then all 2s, without using a library sort. Aim for a single pass and O(1) extra space.
This is the Dutch national flag problem: partition an array into three groups in one pass. The same three-way partition powers quicksort with many duplicate keys and "move all X to the front, Y to the back" questions. Original problem: LeetCode 75.
Example

Input: [2, 0, 1, 1, 0, 2, 1]
Output: [0, 0, 1, 1, 1, 2, 2]
Input: [1, 2, 0]
Output: [0, 1, 2]
Constraints (assumed)
- 1 ≤ n ≤ 300 (the algorithm is O(n) for any n); every value is 0, 1 or 2.
- Modify the array in place; return nothing.
What this question tests
- Keeping loop invariants for three regions with three pointers.
- Knowing which pointer to move after each swap, and why.
- Comparing a two-pass counting sort with the one-pass partition.
Questions to ask first
- Are the values always exactly 0, 1 and 2? (Here: yes.)
- Is one pass required, or are two passes fine? Counting sort in two passes is the easy answer.
- Must it be stable? Equal values are indistinguishable here, so no; with real records it would matter.
- In place? (Here: yes, O(1) extra space.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.