Dutch National Flag Three Way Partition in DSA Python - Build from Scratch

Dutch National Flag Three Way Partition

📖 Scenario: You are organizing colored balls represented by numbers 0, 1, and 2 in a line. You want to group all balls of the same color together in order: all 0s first, then all 1s, and finally all 2s.

🎯 Goal: Build a program that rearranges a list of numbers containing only 0s, 1s, and 2s so that all 0s come first, then all 1s, and then all 2s. This is called the Dutch National Flag problem.

📋 What You'll Learn

Create a list called balls with the exact values: [2, 0, 2, 1, 1, 0]

Create three variables called low, mid, and high with the exact values: 0, 0, and len(balls) - 1 respectively

Use a while loop with the condition mid <= high to rearrange the list using the Dutch National Flag algorithm

Print the balls list after rearrangement

💡 Why This Matters

🌍 Real World

Sorting colored objects or grouping items by categories quickly without using extra space.

💼 Career

Understanding this algorithm helps in coding interviews and problems involving sorting or partitioning data efficiently.

1

Create the initial list of balls

Create a list called balls with these exact values: [2, 0, 2, 1, 1, 0]

DSA Python

# Create the list called balls with the values [2, 0, 2, 1, 1, 0]
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Set up pointers for partitioning

Create three variables called low, mid, and high with the exact values: 0, 0, and len(balls) - 1 respectively

DSA Python

balls = [2, 0, 2, 1, 1, 0]
# Create variables low, mid, and high as described
# Your code here

Hint

Remember that len(balls) gives the number of items in the list.

3

Rearrange the list using the Dutch National Flag algorithm

Use a while loop with the condition mid <= high to rearrange the balls list so that all 0s come first, then 1s, then 2s. Use low, mid, and high to track positions and swap elements as needed.

DSA Python

balls = [2, 0, 2, 1, 1, 0]
low = 0
mid = 0
high = len(balls) - 1
# Use a while loop with condition mid <= high to rearrange balls
# Your code here

Hint

Use swapping to move 0s to the front and 2s to the end. Increase mid when you see 0 or 1, but decrease high when you swap with 2.

4

Print the rearranged list

Print the balls list after rearrangement using print(balls)

DSA Python

balls = [2, 0, 2, 1, 1, 0]
low = 0
mid = 0
high = len(balls) - 1

while mid <= high:
    if balls[mid] == 0:
        balls[low], balls[mid] = balls[mid], balls[low]
        low += 1
        mid += 1
    elif balls[mid] == 1:
        mid += 1
    else:  # balls[mid] == 2
        balls[mid], balls[high] = balls[high], balls[mid]
        high -= 1

# Print the balls list
# Your code here

Hint

Use print(balls) to show the final list.

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