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].