Dutch National Flag Three Way Partition in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on a given list

What is the output of the following code that partitions the list around the pivot value 2?

DSA Python

def dutch_national_flag(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:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

arr = [3, 5, 2, 1, 2, 4, 2]
dutch_national_flag(arr, 2)
print(arr)

A [1, 2, 2, 2, 4, 5, 3]

B [1, 2, 2, 2, 5, 4, 3]

C [2, 2, 2, 1, 3, 4, 5]

D [1, 2, 2, 2, 4, 3, 5]

💡 Hint

Focus on how elements less than, equal to, and greater than the pivot are rearranged.

The algorithm moves all elements less than 2 to the front, equal to 2 in the middle, and greater than 2 at the end. The final order is [1, 2, 2, 2, 4, 5, 3].

🧠 Conceptual

intermediate

Understanding the pointers in Dutch National Flag algorithm

In the Dutch National Flag algorithm, what is the role of the 'mid' pointer during the partitioning process?

A It keeps track of the number of elements equal to the pivot.

B It marks the boundary between elements less than and equal to the pivot.

C It scans through the array to examine each element and decide its position.

D It points to the last element greater than the pivot.

💡 Hint

Think about which pointer moves through the array checking elements.

The 'mid' pointer moves from start to end, examining each element to decide if it should be swapped to the front, middle, or end.

🔧 Debug

advanced

Identify the error in this Dutch National Flag implementation

What error will this code produce when run, and why?

DSA Python

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:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

arr = [2, 1, 3]
dnf(arr, 2)
print(arr)

A TypeError because of swapping elements of different types

B IndexError because 'high' is initialized to len(arr) instead of len(arr) - 1

C Infinite loop because 'mid' is never incremented

D No error, outputs [1, 2, 3]

💡 Hint

Check the initial value of 'high' and how it is used as an index.

The 'high' pointer is set to len(arr), which is out of range for indexing, causing IndexError when accessed.

🚀 Application

advanced

Applying Dutch National Flag to sort colors

Given an array representing colors as 0 (red), 1 (white), and 2 (blue), which option correctly sorts the array using Dutch National Flag algorithm?

DSA Python

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)

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

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

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

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

💡 Hint

Remember the order: red (0), white (1), blue (2).

The algorithm sorts colors by moving 0s to front, 2s to end, and 1s stay in middle, resulting in [0, 0, 1, 1, 2, 2].

❓ Predict Output

expert

Final state of array after Dutch National Flag partition with duplicates

What is the final state of the array after running the Dutch National Flag partition with pivot 3 on this input?

DSA Python

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:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

arr = [4, 3, 2, 3, 1, 4, 3, 2]
dnf_partition(arr, 3)
print(arr)

A [2, 2, 1, 3, 3, 3, 4, 4]

B [1, 2, 3, 3, 3, 2, 4, 4]

C [1, 2, 2, 3, 3, 3, 4, 4]

D [2, 1, 2, 3, 3, 3, 4, 4]

💡 Hint

Check how duplicates of pivot are grouped in the middle.

All elements less than 3 come first (2, 2, 1), then all 3s, then elements greater than 3 (4, 4). The final order is [2, 2, 1, 3, 3, 3, 4, 4].

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