Array
Low Pointer
0
Next position for 0
Mid Pointer
0
Current element
High Pointer
-
Next position for 2
Red (0s)
[0, low)
White (1s)
[low, mid)
Blue (2s)
(high, end]
Click "Step" or "Play" to start the visualization
0 (Red)
1 (White)
2 (Blue)
▲ low - boundary for 0s
▲ mid - current scan
▲ high - boundary for 2s
Python Code - Dutch National Flag Algorithm
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1