Dutch National Flag Three Way Partition in DSA Go - Time & Space Complexity

Time Complexity: Dutch National Flag Three Way Partition

O(n)

Understanding Time Complexity

We want to understand how the time needed to rearrange an array into three parts grows as the array gets bigger.

Specifically, how does the sorting into three groups affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func dutchFlagPartition(arr []int, pivot int) {
    low, mid, high := 0, 0, len(arr)-1
    for mid <= high {
        if arr[mid] < pivot {
            arr[low], arr[mid] = arr[mid], arr[low]
            low++
            mid++
        } else if arr[mid] == pivot {
            mid++
        } else {
            arr[mid], arr[high] = arr[high], arr[mid]
            high--
        }
    }
}
    

This code rearranges the array so that all elements less than the pivot come first, then elements equal to the pivot, then elements greater than the pivot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single while loop scanning the array with pointers.
• How many times: Each element is visited at most once during the traversal; swaps may occur but do not increase the overall complexity.

How Execution Grows With Input

As the array size grows, the number of operations grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 to 20 operations
100	About 100 to 200 operations
1000	About 1000 to 2000 operations

Pattern observation: The work grows linearly with input size, doubling the input roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to rearrange grows directly with the number of elements in the array.

Common Mistake

[X] Wrong: "Because there are nested ifs, the time complexity must be quadratic O(n²)."

[OK] Correct: The loop runs only once through the array, and the ifs just decide swaps without extra loops inside, so the total work is linear.

Interview Connect

Understanding this linear-time partitioning is a great skill for sorting and searching problems, showing you can handle multiple groups efficiently.

Self-Check

"What if we changed the pivot to be the median of the array? How would the time complexity change?"

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To reverse the elements of an array

B. To sort an array in ascending order using quicksort

C. To find the maximum element in an array

D. To rearrange an array so that elements less than, equal to, and greater than a pivot are grouped separately

Solution

1. Step 1: Understand the problem goal

   The Dutch National Flag algorithm partitions an array into three parts based on a pivot value: less than, equal to, and greater than the pivot.

2. Step 2: Compare with other options

   The other options describe different operations: sorting, finding max, and reversing, which are not the main goal here.

3. Final Answer:

   To rearrange an array so that elements less than, equal to, and greater than a pivot are grouped separately -> Option D

4. Quick Check:

   Partitioning array by pivot = A [OK]

Hint: Remember: three groups around pivot, not full sorting [OK]

Common Mistakes:

• Confusing partition with full sorting
• Thinking it only separates two groups
• Assuming it finds max or min values

2. Which of the following Go code snippets correctly initializes the pointers for the Dutch National Flag algorithm on an array arr?

easy

A. low, mid, high := 0, len(arr), len(arr)-1

B. low, mid, high := 0, 0, len(arr)-1

C. low, mid, high := -1, 0, len(arr)

D. low, mid, high := 1, 1, len(arr)-1

Solution

1. Step 1: Identify correct pointer initialization

   In Dutch National Flag, low and mid start at 0, high at last index len(arr)-1.

2. Step 2: Check each option

   low, mid, high := 0, 0, len(arr)-1 matches this. low, mid, high := -1, 0, len(arr) uses invalid indices (-1 and len(arr)). low, mid, high := 0, len(arr), len(arr)-1 sets mid to len(arr) which is out of range. low, mid, high := 1, 1, len(arr)-1 starts pointers at 1, skipping first element.

3. Final Answer:

   low, mid, high := 0, 0, len(arr)-1 -> Option B

4. Quick Check:

   Correct pointer start = C [OK]

Hint: Pointers start at array ends: low=0, mid=0, high=last index [OK]

Common Mistakes:

• Setting mid or high out of array bounds
• Starting pointers at 1 instead of 0
• Using negative indices in Go arrays

3. What will be the output of the following Go code after applying the Dutch National Flag algorithm with pivot = 1?

arr := []int{2, 0, 1, 2, 1, 0}
low, mid, high := 0, 0, len(arr)-1
pivot := 1
for mid <= high {
  if arr[mid] < pivot {
    arr[low], arr[mid] = arr[mid], arr[low]
    low++
    mid++
  } else if arr[mid] == pivot {
    mid++
  } else {
    arr[mid], arr[high] = arr[high], arr[mid]
    high--
  }
}
fmt.Println(arr)

medium

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

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

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

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

Solution

1. Step 1: Trace the partition process

   Initial array: [2, 0, 1, 2, 1, 0]. Pivot = 1. The algorithm moves elements less than 1 to front, equal in middle, greater at end.

2. Step 2: Final array after partition

   After processing, array becomes [0, 0, 1, 1, 2, 2], grouping 0s, then 1s, then 2s.

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option A

4. Quick Check:

   Partitioned array = [0, 0, 1, 1, 2, 2] [OK]

Hint: Group less, equal, greater than pivot in one pass [OK]

Common Mistakes:

• Not swapping correctly when arr[mid] > pivot
• Incrementing mid incorrectly after swap
• Confusing pivot value with array elements

4. Identify the bug in this Go code snippet implementing Dutch National Flag partition:

arr := []int{1, 2, 0, 1, 2}
low, mid, high := 0, 0, len(arr)-1
pivot := 1
for mid < high {
  if arr[mid] < pivot {
    arr[low], arr[mid] = arr[mid], arr[low]
    low++
    mid++
  } else if arr[mid] == pivot {
    mid++
  } else {
    arr[mid], arr[high] = arr[high], arr[mid]
    high--
  }
}
fmt.Println(arr)

medium

A. The pivot value is incorrect

B. Pointers low and mid are initialized incorrectly

C. The loop condition should be 'mid <= high' instead of 'mid < high'

D. Swapping elements is done in wrong order

Solution

1. Step 1: Analyze loop condition

   The loop uses 'mid < high', which misses processing when mid equals high. It should be 'mid <= high' to cover all elements.

2. Step 2: Check other parts

   Pivot is correct, pointers initialized properly, and swapping order is correct. Only loop condition is wrong.

3. Final Answer:

   The loop condition should be 'mid <= high' instead of 'mid < high' -> Option C

4. Quick Check:

   Loop must cover mid = high index [OK]

Hint: Use 'mid <= high' to process all elements including last [OK]

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pivot unnecessarily
• Incorrect pointer initialization

5. Given an array arr containing only 0s, 1s, and 2s, how can you modify the Dutch National Flag algorithm to count the number of swaps performed during partitioning?

medium

A. Add a swap counter variable and increment it each time a swap occurs inside the loop

B. Count swaps only when elements are equal to the pivot

C. Increment counter only when mid pointer moves forward

D. Use a separate loop after partition to count swaps

Solution

1. Step 1: Understand swap counting

   Swaps happen when elements are exchanged. To count them, add a variable initialized to zero before the loop.

2. Step 2: Increment counter on each swap

   Inside the loop, whenever a swap occurs (either arr[low], arr[mid] or arr[mid], arr[high]), increment the counter by one.

3. Final Answer:

   Add a swap counter variable and increment it each time a swap occurs inside the loop -> Option A

4. Quick Check:

   Count swaps during actual swaps [OK]

Hint: Increment counter exactly when swapping elements [OK]

Common Mistakes:

• Counting swaps only for pivot equals
• Counting pointer moves instead of swaps
• Using separate loop to count swaps after partition