Dutch National Flag Three Way Partition in DSA Typescript - 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 sort an array into three parts grows as the array gets bigger.

Specifically, how fast does the Dutch National Flag algorithm run when dividing the array into three groups?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function dutchNationalFlag(arr: number[], pivot: number): void {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] < pivot) {
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      low++; mid++;
    } else if (arr[mid] > pivot) {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    } else {
      mid++;
    }
  }
}
    

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: The while loop that moves the mid pointer through the array.
• How many times: Each element is visited at most once by mid, so the loop runs roughly n times where n is the array length.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly the same amount.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

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

Final Time Complexity

Time Complexity: O(n)

This means the algorithm processes each element once, so the time grows directly with the number of elements.

Common Mistake

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

[OK] Correct: Each element is swapped at most once or twice, and the mid pointer moves forward without repeating elements, so the total steps stay 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 algorithm to use two passes instead of one? 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 rearrange an array into three parts: less than, equal to, and greater than a pivot

D. To find the maximum element in an array

Solution

1. Step 1: Understand the algorithm's purpose and partitioning criteria

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

2. Final Answer:

   To rearrange an array into three parts: less than, equal to, and greater than a pivot -> Option C

3. Quick Check:

   Partitioning = Rearranging into three parts [OK]

Hint: Remember: three parts based on pivot comparison [OK]

Common Mistakes:

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

2. Which of the following is the correct TypeScript syntax to swap two elements arr[i] and arr[j] in an array?

easy

A. const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Understand swapping in TypeScript and verify correct code

   TypeScript does not support tuple unpacking like Python, so use a temporary variable. const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; ensures correct swap.

2. Final Answer:

   const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

3. Quick Check:

   Temporary variable swap = const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use a temp variable to swap two elements safely [OK]

Common Mistakes:

• Using Python-style tuple unpacking syntax
• Overwriting one element before saving it
• Calling undefined swap functions

3. What will be the output array after applying the Dutch National Flag algorithm on arr = [2, 0, 2, 1, 1, 0] with pivot = 1?

medium

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

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

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

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

Solution

1. Step 1: Partition elements and arrange array

   Elements less than 1: 0, 0; equal to 1: 1, 1; greater than 1: 2, 2. Arrange as [less than] + [equal] + [greater than]: [0, 0, 1, 1, 2, 2].

2. Final Answer:

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

3. Quick Check:

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

Hint: Group by less, equal, greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Assuming full sort instead of partition

4. Given this TypeScript code snippet for Dutch National Flag partition, what is the bug?

function dnfPartition(arr: number[], pivot: number): void {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] < pivot) {
      const temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
      low++;
    } else if (arr[mid] === pivot) {
      mid++;
    } else {
      const temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
      high--;
    }
  }
}

medium

A. Missing increment of mid after swapping when arr[mid] < pivot

B. Incorrect comparison operators used

C. Should decrement low instead of increment

D. Loop condition should be mid < high, not mid <= high

Solution

1. Step 1: Analyze the swap when arr[mid] < pivot and identify effect

   After swapping arr[low] and arr[mid], low++ but missing mid++, causing the loop to recheck the same mid index, leading to infinite loop or wrong behavior.

2. Final Answer:

   Missing increment of mid after swapping when arr[mid] < pivot -> Option A

3. Quick Check:

   mid++ needed after swap when arr[mid] < pivot [OK]

Hint: Always increment mid after swapping with low [OK]

Common Mistakes:

• Forgetting to increment mid after swap
• Changing loop condition incorrectly
• Misusing comparison operators

5. You have an array arr = [3, 5, 2, 1, 4, 3, 2] and want to partition it using the Dutch National Flag algorithm with pivot = 3. After partitioning, which of the following is a valid output?

hard

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

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

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

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

Solution

1. Step 1: Identify groups based on pivot 3 and check options

   Less than 3: 1, 2, 2; equal to 3: 3, 3; greater than 3: 4, 5. Valid output must have all less, then all equal, then all greater.
   A: [1, 2, 2, 3, 3, 4, 5] valid.
   B: equals first, invalid.
   C: [2, 1, 3, 2, 3, 4, 5] has 2 (<3) after 3's, invalid.
   D: greater before equals, invalid.

2. Final Answer:

   [1, 2, 2, 3, 3, 4, 5] -> Option B

3. Quick Check:

   Partition order: less, equal, greater [OK]

Hint: Partition order must be less, equal, then greater [OK]

Common Mistakes:

• Placing equal elements at wrong position
• Confusing full sort with partition
• Ignoring group order rules