</>EmbeddedInterview
← All problems · Arrays & Searching

Sort 0s, 1s and 2s in One Pass (Dutch National Flag)

Medium

An array contains only the values 0, 1 and 2. Sort it in place in a single pass with O(1) extra memory and without counting.

Implement void sort_012(int *a, size_t n).

Example: {2, 0, 2, 1, 1, 0} → {0, 0, 1, 1, 2, 2}.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Use three indexes: everything before low is 0, everything after high is 2, and mid scans the unknown middle. A 0 is swapped to low, a 2 is swapped to high, a 1 stays. After swapping with high, do not advance mid: the value you swapped in is still unchecked.

#include <stdio.h>
#include <stddef.h>
#include <string.h>

static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }

void sort_012(int *a, size_t n)
{
    if (n == 0) return;
    size_t low = 0, mid = 0, high = n - 1;

    while (mid <= high) {
        if (a[mid] == 0) {
            swap(&a[low++], &a[mid++]);
        } else if (a[mid] == 1) {
            mid++;
        } else {                       /* a[mid] == 2 */
            swap(&a[mid], &a[high]);
            if (high == 0) break;      /* avoid size_t underflow */
            high--;                    /* mid stays: new a[mid] is unchecked */
        }
    }
}

Dijkstra's Dutch National Flag algorithm keeps four regions at all times:

[0 .. low-1]   all 0s
[low .. mid-1] all 1s
[mid .. high]  not yet examined
[high+1 .. n-1] all 2s

Each step shrinks the unknown region by one, so it is one pass, O(n) time, O(1) memory.

Walk-through: {2, 0, 2, 1, 1, 0}

low mid high a[mid] action array
0 0 5 2 swap mid↔high, high-- 0 0 2 1 1 2
0 0 4 0 swap low↔mid, low++, mid++ 0 0 2 1 1 2
1 1 4 0 swap low↔mid, low++, mid++ 0 0 2 1 1 2
2 2 4 2 swap mid↔high, high-- 0 0 1 1 2 2
2 2 3 1 mid++ 0 0 1 1 2 2
2 3 3 1 mid++ → done 0 0 1 1 2 2

Why mid does not move after the 2-swap: the element brought in from high has not been examined yet; it could be a 0 that must still go left. After a 0-swap, the element coming from low is already known to be a 1 (or it is the same element), so mid can advance.

Watch out in C: with unsigned size_t indexes, high-- when high == 0 wraps to a huge number, so the solution stops explicitly. The original int version avoids this but cannot handle arrays larger than INT_MAX.

Follow-ups: counting sort (two passes) is simpler if a single pass is not required; the same partitioning is the core of three-way quicksort, which handles many duplicate keys efficiently; "move all zeros to the end" and "segregate even/odd" are two-region versions.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    int a[] = { 2, 0, 2, 1, 1, 0 };
    const int ea[] = { 0, 0, 1, 1, 2, 2 };
    sort_012(a, 6); CHECK(memcmp(a, ea, sizeof ea) == 0);
    int b[] = { 2, 2, 2 };
    sort_012(b, 3); CHECK(b[0] == 2 && b[2] == 2);
    int c[] = { 2, 1, 0 };
    const int ec[] = { 0, 1, 2 };
    sort_012(c, 3); CHECK(memcmp(c, ec, sizeof ec) == 0);
    int d[] = { 0 };
    sort_012(d, 1); CHECK(d[0] == 0);
    sort_012(NULL, 0);
    int e[] = { 1, 2, 0, 2, 0, 1, 1, 0, 2, 0 };
    const int ee[] = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 2 };
    sort_012(e, 10); CHECK(memcmp(e, ee, sizeof ee) == 0);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}