AlgoViz
HomeTwo Pointers

Sort Colors

Medium

Dutch National Flag · in-place · three pointers

In simple words

Sweep once and toss every 0 to the front and every 2 to the back, leaving the 1s in the middle.

The idea

Three pointers carve the array into three zones: 0s, 1s, 2s. 'mid' scans; a 0 swaps down to 'low', a 2 swaps up to 'high', a 1 stays put. One pass, no counting.

low
mid
high
2
0
2
1
1
0
0
1
2
3
4
5

Step 1 of 8. Three regions: 0s before low, 2s after high, unknown in the middle. "mid" scans. Values: 2, 0, 2, 1, 1, 0. Pointers: low at index 0, mid at index 0, high at index 5.

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, then 1s, then 2s.

Example 2

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

Example 3

Input:
nums = [1, 0]
Output:
[0, 1]
Explanation:
Two colours swap into order.

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

Finished the walkthrough? Add it to your streak.