Dutch National Flag Three Way Partition in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Dutch National Flag problem?

To rearrange an array with three distinct values so that all elements of the first value come first, followed by all elements of the second value, and then all elements of the third value.

beginner

Which three pointers are used in the Dutch National Flag algorithm?

Low (start of first section), Mid (current element), and High (end of third section).

intermediate

In the Dutch National Flag algorithm, what happens when the mid pointer points to the lowest value?

Swap the element at mid with the element at low, then increment both low and mid pointers.

intermediate

Why does the Dutch National Flag algorithm only require one pass through the array?

Because it uses three pointers to partition the array in-place, moving elements to their correct sections as it goes, avoiding multiple scans.

beginner

What is the time complexity of the Dutch National Flag algorithm?

O(n), where n is the number of elements in the array, since it processes each element at most once.

What does the 'low' pointer represent in the Dutch National Flag algorithm?

A The boundary between the second and third sections

B The current element being processed

C The boundary between the first and second sections

D The last element of the array

The 'low' pointer marks the boundary between the first section (lowest values) and the middle section.

When the element at 'mid' is the highest value, what action is taken?

A Swap with element at 'low' and increment both 'low' and 'mid'

B Swap with element at 'high' and increment 'mid'

C Increment 'mid' only

D Swap with element at 'high' and decrement 'high' only

When 'mid' points to the highest value, swap it with 'high' and decrement 'high' to move the highest values to the end.

What is the initial position of the 'high' pointer?

A At the end of the array

B At the middle of the array

C At the start of the array

D One position after the end of the array

'High' starts at the last index of the array to track the boundary of the highest values.

Which of these is NOT a benefit of the Dutch National Flag algorithm?

A Works only for arrays with two distinct values

B Single pass through the array

C Linear time complexity

D In-place sorting without extra space

The algorithm is designed for three distinct values, not just two.

What happens to the 'mid' pointer when the element at 'mid' is the middle value?

A It is swapped with 'high' and 'high' decremented

B It is incremented without swapping

C It is swapped with 'low' and both pointers incremented

D It is decremented

When 'mid' points to the middle value, just move 'mid' forward to process the next element.

Explain the step-by-step process of the Dutch National Flag algorithm using the three pointers.

Think about how each pointer moves and how swaps help separate the three groups.

Describe a real-life scenario where the Dutch National Flag problem analogy can be applied.

Imagine sorting colored balls or organizing files into three folders.

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