Dutch Flag Problem

Given an array consisting of letters 'R', 'W', and 'B', sort it in place to put all the 'R' before all the 'W' and all the 'W' before all the 'B'.

Example:

  • Input: arr = ['R', 'W', 'B', 'W', 'R', 'B', 'W']
  • Output: ['R', 'R', 'W', 'W', 'W', 'B', 'B']
1def dutchFlagSort(arr: List[str]) -> None:
2    low, mid, high = 0, 0, len(arr) - 1
3    
4    while mid <= high:
5        if arr[mid] == 'R':
6            arr[low], arr[mid] = arr[mid], arr[low]
7            low += 1
8            mid += 1
9        elif arr[mid] == 'W':
10            mid += 1
11        else: # arr[mid] == 'B'
12            arr[high], arr[mid] = arr[mid], arr[high]
13            high -= 1
Previous
Quicksort Partition
Next
Prefix-Suffix Swap
low
mid
R
0
W
1
B
2
W
3
R
4
B
5
high
W
6
Step 1 / 3
Step 1:
Initialize low=0, mid=0, high=6.
Pointers: high=6, low=0, mid=0
Focus: select @ [0, 6]