Dutch National Flag Algorithm

The Dutch National Flag algorithm was proposed by Edsger Dijkstra to sort an array with three distinct values. The most common example is sorting an array containing only 0, 1 and 2. The algorithm efficiently sorts the array in a single pass.

Problem description

Given an array of n elements where each element is either 0, 1 or 2, the goal is to sort the array such that all 0s come first, followed by 1s and then all 2s.

Concept

The Dutch National Flag problem divides the array into three partitions:

• Low: contains all 0s
• Mid: contains all 1s
• High: contains all 2s

Approach

We use three pointers: low, mid and high. low tracks the boundary where 0s should end. mid traverses through the array. high tracks the boundary where 2s should begin.

The algorithm processes the array in one pass:

• If the current element is 0: swap it with the element at low, then increment both low and mid
• If the current element is 1: leave it in place and just move the mid pointer.
• If the current element is 2: swap it with the element at high and decrement high

Code

def dutch_national_flag(arr):
	low, mid = 0, 0
	high = len(arr) - 1
	
	while mid <= high:
		if arr[mid] == 0:
			arr[low], arr[mid] = arr[mid], arr[low]
			low += 1
			mid += 1
		elif arr[mid] == 1:
			mid += 1
		else:
			arr[mid], arr[high] = arr[high], arr[mid]
			high -= 1
		
		return arr

Time Complexity:

The time complexity of Dutch National Flag algorithm is O(n)

Space Complexity:

The space complexity of Dutch National Flag algorithm is O(1)