Dutch National Flag Three Way Partition in DSA Python

Mental Model

We divide an array into three parts by moving elements less than, equal to, and greater than a pivot value into separate sections in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick one ball at a time and put it in the correct bin without mixing them up.

Array: [ 2, 0, 2, 1, 1, 0 ]
Indexes:  0  1  2  3  4  5
Pointers:
  low ↑    mid ↑          high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0], pivot = 1

Goal: Rearrange array so all elements < 1 come first, then all elements == 1, then all elements > 1

Step 1: Check element at mid=0 (value 2), which is > pivot; swap with element at high=5

[0, 0, 2, 1, 1, 2]
low=0 mid=0 high=4

Why: We move larger elements to the end to separate them from smaller ones

Step 2: Check element at mid=0 (value 0), which is < pivot; swap with element at low=0 and move both pointers forward

[0, 0, 2, 1, 1, 2]
low=1 mid=1 high=4

Why: We move smaller elements to the front to group them

Step 3: Check element at mid=1 (value 0), which is < pivot; swap with element at low=1 and move both pointers forward

[0, 0, 2, 1, 1, 2]
low=2 mid=2 high=4

Why: Continue grouping smaller elements at the front

Step 4: Check element at mid=2 (value 2), which is > pivot; swap with element at high=4

[0, 0, 1, 1, 2, 2]
low=2 mid=2 high=3

Why: Move larger elements to the end

Step 5: Check element at mid=2 (value 1), which is == pivot; move mid pointer forward

[0, 0, 1, 1, 2, 2]
low=2 mid=3 high=3

Why: Elements equal to pivot stay in the middle

Step 6: Check element at mid=3 (value 1), which is == pivot; move mid pointer forward

[0, 0, 1, 1, 2, 2]
low=2 mid=4 high=3

Why: All elements processed; partition complete

Result:

[0, 0, 1, 1, 2, 2]

Annotated Code

DSA Python

from typing import List

class DutchNationalFlag:
    @staticmethod
    def three_way_partition(arr: List[int], pivot: int) -> None:
        low, mid, high = 0, 0, len(arr) - 1
        while mid <= high:
            if arr[mid] < pivot:
                arr[low], arr[mid] = arr[mid], arr[low]
                low += 1
                mid += 1
            elif arr[mid] == pivot:
                mid += 1
            else:
                arr[mid], arr[high] = arr[high], arr[mid]
                high -= 1

if __name__ == '__main__':
    arr = [2, 0, 2, 1, 1, 0]
    pivot = 1
    DutchNationalFlag.three_way_partition(arr, pivot)
    print(arr)

while mid <= high:

continue partitioning until mid passes high

if arr[mid] < pivot:

if current element is less than pivot, swap to front and move low and mid forward

arr[low], arr[mid] = arr[mid], arr[low]

swap smaller element to low partition

low += 1 mid += 1

advance low and mid pointers after placing smaller element

elif arr[mid] == pivot:

if element equals pivot, just move mid forward

mid += 1

advance mid pointer to check next element

else:

if element greater than pivot, swap with high and move high backward

arr[mid], arr[high] = arr[high], arr[mid] high -= 1

swap larger element to end and reduce high pointer

Output

[0, 0, 1, 1, 2, 2]

Complexity Analysis

Time: O(n) because we scan the array once with pointers moving forward or backward

Space: O(1) because partitioning is done in place without extra storage

vs Alternative: Compared to sorting the entire array (O(n log n)), this approach is faster and more efficient for three-way partitioning

Edge Cases

empty array

function completes immediately without changes

DSA Python

while mid <= high:

all elements equal to pivot

mid pointer moves through all elements without swaps

DSA Python

elif arr[mid] == pivot:

no elements less than pivot

only swaps between mid and high for elements greater than pivot

DSA Python

else:

When to Use This Pattern

When you need to separate an array into three groups around a pivot in one pass, use the Dutch National Flag pattern for efficient partitioning.

Common Mistakes

Mistake: Advancing mid pointer after swapping with high without checking the swapped element
Fix: Do not advance mid after swapping with high because the swapped element needs to be checked

Summary

Rearranges an array into three parts: less than, equal to, and greater than a pivot.

Use when you want to partition data efficiently in one pass without full sorting.

The key is using three pointers to track boundaries and carefully swapping elements.