Dutch Flag Problem

01 · Question

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']

02 · Solution

Reference solution

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

Quicksort Partition

Prefix-Suffix Swap