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.