Dutch National Flag Problem – Explanation and Python/Go Solutions

Today marks day 93 of the "365 problem solving plan", introducing the classic Dutch National Flag problem originally proposed by Edsger Dijkstra, where balls of three colors (red, white, blue) must be sorted.

The problem can be visualized as arranging the colors to form the Dutch flag, requiring partitioning the array into three sections using two pointers (A and B) and a scanning pointer C.

Three cases are considered during the scan: when the current element is 0 (red) it is swapped with the element at pointer A and both A and C advance; when it is 2 (blue) it is swapped with the element at pointer B and B moves left while C stays; when it is 1 (white) no action is needed other than advancing C.

The algorithm runs in O(n) time with O(1) extra space. Below are concise implementations in Python and Go.

1//py3
2class Solution:
3    def sortColors(self, nums: List[int]) -> None:
4        a = c = 0
5        b = len(nums) - 1
6        while c <= b:
7            if nums[c] == 0:
8                nums[a], nums[c] = nums[c], nums[a]
9                a += 1
10                c += 1
11            elif nums[c] == 2:
12                nums[c], nums[b] = nums[b], nums[c]
13                b -= 1
14            else:
15                c += 1

//go
func sortColors(nums []int) {
    a := 0
    b := len(nums) - 1
    for c := 0; c <= b; c++ {
        if nums[c] == 0 {
            nums[c], nums[a] = nums[a], nums[c]
            a++
        }
        if nums[c] == 2 {
            nums[c], nums[b] = nums[b], nums[c]
            c--
            b--
        }
    }
}

The article concludes that the solution is simple yet effective, and the code has been tested on LeetCode.