Visualize

Pattern visualizer

Sort an Array of 0s 1s and 2s

Only three distinct values exist, so no comparison sort is needed — the array can partition itself. Grow three regions at once: settled 0s left of low, settled 2s right of high, and an unknown band low..high that shrinks on every look. A 0 is swapped to the front, a 2 is thrown to the back, a 1 is already home. The one rule that decides whether the code is correct: after swapping a 2 backwards, mid must NOT advance, because the value that came back from the right end has never been examined. Animated on: nums = [0,2,1,2,0,1,2,0] — sort it in place in a single pass, without counting the values first..

Dutch national flag — one pass, three regions

time O(n)space O(1)step 1 / 10
0
[0]
2
[1]
1
[2]
2
[3]
0
[4]
1
[5]
2
[6]
0
[7]
line 4

Three regions, not a sort. Everything left of low is a settled 0, everything right of high is a settled 2, and low..high is still unknown. low=0, mid=0 and high=7 start with the whole array unknown, so nothing is settled yet.

Pseudocode
1FUNCTION sortColors(nums)
2  low <- 0
3  mid <- 0
4  high <- LENGTH(nums) - 1
5  WHILE mid <= high
6    IF nums[mid] = 2
7      SWAP nums[mid] AND nums[high]
8      high <- high - 1
9    ELSE
10      IF nums[mid] = 0
11        SWAP nums[low] AND nums[mid]
12        low <- low + 1
13      mid <- mid + 1

← / → step · space play · Home restart

Where to practice Arrays

Practice Arrays problemsAll Arrays problemsBack to roadmap