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.

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To sort an array in ascending order using bubble sort.

B. To find the maximum element in an array.

C. To rearrange an array so that all elements less than a pivot come first, followed by elements equal to the pivot, then elements greater than the pivot.

D. To reverse the elements of an array.

Solution

1. Step 1: Understand the partitioning goal

   The algorithm divides the array into three parts based on a pivot: less than, equal to, and greater than the pivot.

2. Step 2: Recognize the rearrangement process

   The array is rearranged so that all smaller elements come first, then equal, then larger elements.

3. Final Answer:

   To rearrange an array so that all elements less than a pivot come first, followed by elements equal to the pivot, then elements greater than the pivot. -> Option C

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

Hint: Remember: three parts - less, equal, greater [OK]

Common Mistakes:

• Confusing it with full sorting algorithms
• Thinking it only separates two groups
• Assuming it finds max or min values

2. Which of the following is the correct way to initialize pointers for the Dutch National Flag algorithm in Python?

easy

A. low = 0; mid = len(arr) - 1; high = 0

B. low = 1; mid = 1; high = len(arr)

C. low = len(arr); mid = 0; high = 0

D. low = 0; mid = 0; high = len(arr) - 1

Solution

1. Step 1: Identify correct pointer initialization

   In the algorithm, low and mid start at 0, and high starts at the last index (length - 1).

2. Step 2: Check each option

   low = 0; mid = 0; high = len(arr) - 1 correctly sets low=0, mid=0, high=len(arr)-1; others have invalid or reversed values.

3. Final Answer:

   low = 0; mid = 0; high = len(arr) - 1 -> Option D

4. Quick Check:

   Pointers start at array ends and middle [OK]

Hint: Start low and mid at 0, high at last index [OK]

Common Mistakes:

• Setting pointers outside array bounds
• Starting mid or low at wrong index
• Confusing high pointer initialization

3. What will be the output of the following code snippet?

def dnf_partition(arr, pivot):
    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

arr = [2, 0, 2, 1, 1, 0]
dnf_partition(arr, 1)
print(arr)

medium

A. [0, 0, 1, 1, 2, 2]

B. [1, 1, 0, 0, 2, 2]

C. [2, 2, 1, 1, 0, 0]

D. [0, 1, 0, 1, 2, 2]

Solution

1. Step 1: Trace the partitioning process

   Initial array: [2, 0, 2, 1, 1, 0], pivot=1. The algorithm moves elements less than 1 to front, equal to middle, greater to end.

2. Step 2: Final array after partition

   After processing, array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option A

4. Quick Check:

   Partitioned array = [0, 0, 1, 1, 2, 2] [OK]

Hint: Swap less than pivot left, greater right [OK]

Common Mistakes:

• Not swapping correctly when arr[mid] > pivot
• Incrementing mid incorrectly after swap
• Confusing pivot equality handling

4. Identify the error in this Dutch National Flag partition code:

def dnf(arr, pivot):
    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

medium

A. The while loop condition should be 'mid <= high' instead of 'mid < high'.

B. Pointers low and mid are initialized incorrectly.

C. The swap operation for elements less than pivot is missing.

D. The pivot value is not used in comparisons.

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'mid < high', which misses processing when mid equals high, leaving last element unchecked.

2. Step 2: Correct loop condition

   Changing to 'mid <= high' ensures all elements are processed including the last one.

3. Final Answer:

   The while loop condition should be 'mid <= high' instead of 'mid < high'. -> Option A

4. Quick Check:

   Loop must cover all elements [OK]

Hint: Use 'mid <= high' to cover all elements [OK]

Common Mistakes:

• Using '<' instead of '<=' in loop condition
• Forgetting to increment mid after swaps
• Incorrect pointer initialization

5. Given an array with elements 0, 1, and 2 representing colors red, white, and blue respectively, how would you modify the Dutch National Flag algorithm to sort the array in-place so that all reds come first, whites second, and blues last? Choose the best approach.

hard

A. Sort the array using built-in sort function for simplicity.

B. Use three pointers low, mid, high; swap elements less than 1 to front, equal to 1 stay in middle, greater than 1 to end.

C. Use two pointers only, swapping elements randomly until sorted.

D. Count the number of 0s, 1s, and 2s, then overwrite the array with counted values.

Solution

1. Step 1: Understand the problem context

   We want to sort colors represented by 0,1,2 in order red(0), white(1), blue(2) using Dutch National Flag algorithm.

2. Step 2: Apply three-pointer partitioning

   Using low, mid, high pointers and pivot=1, swap elements less than 1 to front, equal stay middle, greater to end achieves in-place sorting efficiently.

3. Final Answer:

   Use three pointers low, mid, high; swap elements less than 1 to front, equal to 1 stay in middle, greater than 1 to end. -> Option B

4. Quick Check:

   Three-pointer partition sorts colors in one pass [OK]

Hint: Use pivot=1 and three pointers for one-pass sorting [OK]

Common Mistakes:

• Using built-in sort instead of in-place partition
• Trying two pointers only, which is insufficient
• Counting and overwriting instead of partitioning