DSA Tracker

Visualize

Sort Colors

Dutch national flag — three pointers, one pass

time O(n)space O(1)

With only three possible values, you don't need real sorting — you need three growing regions that never require re-examining a cell twice: settled 0s on the left, settled 2s on the right, and an unknown middle that shrinks with every look. The Dutch national flag partition keeps those three regions growing at once: 0s settle left of low, 2s settle right of high, and mid scans the unknown middle. Each look at nums[mid] either files a 0 to the front, a 2 to the back, or leaves a 1 in place — so the array sorts itself in one sweep.

Details

Animated on: Sort the array [2, 0, 2, 1, 1, 0] of colors (0 = red, 1 = white, 2 = blue) in place, in a single pass, without a counting sort.

Problem:Sort ColorsMedium

Dutch national flag — three pointers, one pass

step 1 / 10

2
[0]
0
[1]
2
[2]
1
[3]
1
[4]
0
[5]

Setup: low = 0 (0s will live left of it), high = 5 (2s will live right of it), mid = 0 scans the unknown zone. Everything between low and high is unsorted.

  • low=0· arr[0] = 2
  • mid=0· arr[0] = 2
  • high=5· arr[5] = 0
Pseudocode
1FUNCTION sortColors(nums):
2  low = 0, mid = 0, high = (the length of nums) - 1
3  WHILE mid <= high:
4    IF nums[mid] equals 0:
5      swap nums[mid] and nums[low]; move low right; move mid right
6    ELSE IF nums[mid] equals 1:
7      move mid one step right
8    ELSE:   (nums[mid] equals 2)
9      swap nums[mid] and nums[high]; move high one step left

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Setup: low = 0 (0s will live left of it), high = 5 (2s will live right of it), mid = 0 scans the unknown zone. Everything between low and high is unsorted.
  2. nums[mid] = nums[0] = 2. A 2 belongs at the back, so swap it with nums[high] = nums[5] = 0. mid must NOT advance — whatever high sends over is still unexamined.
  3. Swapped: [0,0,2,1,1,2]. The 2 is filed at index 5 (settled, never touched again) and high shrinks to 4. mid stays at 0 to inspect the incoming 0.
  4. nums[mid] = 0: it belongs in the front region. low == mid, so swap(0,0) is a no-op — the 0 is already in place. Both advance: low = 1, mid = 1.
  5. nums[1] = 0 again — same move: no-op swap, low = 2, mid = 2. The 0-region [0,0] is locked in at the front; mid can safely advance past a 0 because it was just verified.
  6. nums[mid] = nums[2] = 2. File it at the back: swap with nums[high] = nums[4] = 1. Again mid holds position — the 1 coming in still needs a look.
  7. Swapped: [0,0,1,1,2,2]. The 2-region now spans indices 4-5 and high shrinks to 3. Only indices 2-3 remain unknown.
  8. nums[mid] = nums[2] = 1. A 1 is already where it belongs — between the 0s and the 2s — so no swap at all: just mid = 3. low stays put, marking where the next 0 would go.
  9. nums[3] = 1 too — mid advances to 4. Now mid = 4 has crossed high = 3: the unknown zone is empty, so the while loop ends.
  10. Done: [0,0,1,1,2,2] — 0s at indices 0-1, 1s at 2-3, 2s at 4-5. One pass, constant space, and each element was swapped at most twice.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sort Colors in the editorAll Arrays problemsBack to roadmap