Sort an array of 0s, 1s and 2s

Medium

Problem

The array contains only 0, 1 and 2. Sort it in place in a single pass, without a library sort and without counting then rewriting (the Dutch National Flag problem).

Example 1

Input:  [0, 2, 1, 2, 0]
Output: [0, 0, 1, 2, 2]

Also asked as: Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo

Test cases

Case 1

Input:    [0,2,1,2,0]
Expected: [0,0,1,2,2]

Case 2

Input:    [2,0,1]
Expected: [0,1,2]

Case 3

Input:    [1,1,1]
Expected: [1,1,1]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Dutch National Flag (one pass)

Time O(n)Space O(1)

Three pointers: everything before `low` is 0, after `high` is 2, `mid` scans the unknown middle.

function sort012(a) {
let low = 0, mid = 0, high = a.length - 1;
while (mid <= high) {
if (a[mid] === 0) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; }
else if (a[mid] === 1) mid++;
else { [a[mid], a[high]] = [a[high], a[mid]]; high--; }
}
return a;
}

2. Counting sort

Time O(n)Space O(1)

Count 0s/1s/2s, then overwrite. Two passes, trivial to reason about.

function sort012(a) {
const c = [0, 0, 0];
for (const x of a) c[x]++;
let i = 0;
for (let v = 0; v < 3; v++) while (c[v]-- > 0) a[i++] = v;
return a;
}