Sort Colors

Free with account Updated Nov 19, 2026 · 5 min read
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

    Seven values become three bands: two 0s, three 1s, two 2s.
    Seven values become three bands: two 0s, three 1s, two 2s.
    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

    1. Are the values always exactly 0, 1 and 2? (Here: yes.)
    2. Is one pass required, or are two passes fine? Counting sort in two passes is the easy answer.
    3. Must it be stable? Equal values are indistinguishable here, so no; with real records it would matter.
    4. In place? (Here: yes, O(1) extra space.)