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

Medium

Dutch national flag: three pointers, one pass

Problem

Given an array nums consisting only of 0s, 1s and 2s, sort it in-place in a single pass so that all 0s come first, then all 1s, then all 2s (the Dutch National Flag problem).

In simple words

Use three buckets (0s, 1s, 2s) and lay them down in order in a single pass.

The idea

Maintain three regions with pointers low, mid and high: everything before low is 0, everything after high is 2, and mid scans the unknown middle. Swapping a 2 to the back does not tell you what came back, so mid must not advance in that case — that single asymmetry is the whole algorithm.

The trick

On a 0: swap with low, advance both. On a 1: advance mid. On a 2: swap with high, decrement high only.
Do not advance mid after swapping with high — the incoming value is unexamined.
One pass, O(1) space, versus two passes for a counting sort.

←→stepspaceplay

low

mid

high

1/8

Optimal

timeO(n)spaceO(1)

One pass, three pointers.

1// three regions: 0s | unknown | 2s2let low = 0, mid = 0, high = n - 1;3while (mid <= high) {4  if (nums[mid] === 0) {5    swap(low++, mid++);6  } else if (nums[mid] === 1) {7    mid++;8  } else {9    swap(mid, high--);10  }11}12// now ordered: 0s, then 1s, then 2s

Input

array: [2, 0, 2, 1, 1, 0]

Memory

low: = 0 [2]
mid: = 0 [2]
high: = 5 [0]

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [2, 0, 2, 1, 1, 0]
Output:: [0, 0, 1, 1, 2, 2]
Explanation:: All 0s first, then 1s, then 2s.

Example 2

Input:: nums = [2, 0, 1]
Output:: [0, 1, 2]
Explanation:: Sorted becomes 0, 1, 2.

Example 3

Input:: nums = [0, 0, 0]
Output:: [0, 0, 0]
Explanation:: Already all 0s.

Constraints

1 <= nums.length <= 10^5
nums[i] is 0, 1 or 2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.