Dutch National Flag Three Way Partition in DSA Javascript - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Start with array and pivot

↓

Initialize low=0, mid=0, high=end

↓

Check element at mid

↓

Swap with low

↓

Increment low, mid

↓

Repeat until mid > high

↓

Partition done

The array is divided into three parts by moving elements less than, equal to, and greater than the pivot using three pointers low, mid, and high.

Execution Sample

DSA Javascript

function dutchFlagPartition(arr, pivot) {
  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) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]]; high--;
    }
  }
}

This code partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	6	[2, 0, 2, 1, 1, 0, 2]	low=0, mid=0, high=6
2	arr[mid]=2 > pivot=1, swap arr[mid] and arr[high]	0	0	5	[2, 0, 2, 1, 1, 0, 2]	Swap arr[0] and arr[6], high=5
3	arr[mid]=2 > pivot=1, swap arr[mid] and arr[high]	0	0	4	[0, 0, 2, 1, 1, 2, 2]	Swap arr[0] and arr[5], high=4
4	arr[mid]=0 < pivot=1, swap arr[low] and arr[mid]	1	1	4	[0, 0, 2, 1, 1, 2, 2]	Swap arr[0] and arr[0], low=1, mid=1
5	arr[mid]=0 < pivot=1, swap arr[low] and arr[mid]	2	2	4	[0, 0, 2, 1, 1, 2, 2]	Swap arr[1] and arr[1], low=2, mid=2
6	arr[mid]=2 > pivot=1, swap arr[mid] and arr[high]	2	2	3	[0, 0, 1, 1, 2, 2, 2]	Swap arr[2] and arr[4], high=3
7	arr[mid]=1 == pivot=1, mid++	2	3	3	[0, 0, 1, 1, 2, 2, 2]	mid=3
8	arr[mid]=1 == pivot=1, mid++	2	4	3	[0, 0, 1, 1, 2, 2, 2]	mid=4
9	mid > high, done	2	4	3	[0, 0, 1, 1, 2, 2, 2]	Partition complete

💡 mid (4) > high (3), partitioning finished

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
low	0	0	1	2	2	2
mid	0	0	1	2	4	4
high	6	5	4	3	3	3
Array	[2,0,2,1,1,0,2]	[2,0,2,1,1,0,2]	[0,0,2,1,1,2,2]	[0,0,1,1,2,2,2]	[0,0,1,1,2,2,2]	[0,0,1,1,2,2,2]

Key Moments - 3 Insights

Why do we swap arr[mid] with arr[high] when arr[mid] > pivot instead of incrementing mid?

Because the element swapped from arr[high] is unprocessed, we must check it again at mid before moving mid forward. See steps 2 and 3 in execution_table.

Why do we increment both low and mid when arr[mid] < pivot?

Because after swapping arr[mid] with arr[low], the element at mid is guaranteed to be processed and less than pivot, so we can safely move both pointers forward. See steps 4 and 5.

When does the loop stop and why?

The loop stops when mid > high because all elements beyond high are greater than pivot and all elements before low are less than pivot. See step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value of 'high' after the operation?

A 5

B 3

C 4

D 6

💡 Hint

Check the 'high' column in execution_table row for step 5.

At which step does 'mid' first become greater than 'high'?

A Step 9

B Step 8

C Step 7

D Step 6

💡 Hint

Look at the 'mid' and 'high' values in execution_table rows; step 9 shows mid=4 and high=3.

If the pivot was changed to 2, how would the pointer movement change at step 2?

A Swap would still happen because arr[mid] > pivot

B mid would increment because arr[mid] == pivot

C low and mid would increment because arr[mid] < pivot

D high would decrement without swap

💡 Hint

Check the condition for arr[mid] == pivot in the code and compare with execution_table step 2.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- Elements < pivot go to front (swap with low)
- Elements == pivot stay in middle (mid++)
- Elements > pivot go to end (swap with high)
- Continue until mid > high
- Result: array partitioned into three parts

Full Transcript

The Dutch National Flag algorithm partitions an array into three parts based on a pivot value. We use three pointers: low, mid, and high. Initially, low and mid start at 0, and high at the last index. We check the element at mid: if less than pivot, swap with low and increment both low and mid; if equal, just increment mid; if greater, swap with high and decrement high. We repeat until mid passes high. This ensures all elements less than pivot are at the front, equal in the middle, and greater at the end. The execution table shows each step with pointer positions and array state. Key moments clarify why swaps and pointer moves happen. The quiz tests understanding of pointer changes and loop termination.

Practice

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

easy

A. To find the maximum element in an array

B. To sort an array in ascending order using quicksort

C. To reverse the elements of an array

D. To rearrange an array so that all elements less than a pivot come first, then equal elements, then greater elements

Solution

1. Step 1: Understand the partition goal

   The algorithm divides the array into three parts: less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Identify the rearrangement

   It rearranges elements so that all smaller come first, then equal, then larger, without full sorting.

3. Final Answer:

   To rearrange an array so that all elements less than a pivot come first, then equal elements, then greater elements -> Option D

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

Hint: Remember: three parts - less, equal, greater [OK]

Common Mistakes:

• Confusing partition with full sorting
• Thinking it only finds max or min
• Assuming it reverses the array

2. Which of the following is the correct way to initialize pointers for the Dutch National Flag algorithm in JavaScript?

easy

A. let low = 0, mid = 0, high = arr.length - 1;

B. let low = arr.length - 1, mid = 0, high = 0;

C. let low = 0, mid = arr.length - 1, high = 0;

D. let low = 0, mid = 1, high = arr.length;

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high at last index to cover full array.

2. Step 2: Match initialization to algorithm

   Correct initialization is low=0, mid=0, high=arr.length-1 to scan and partition properly.

3. Final Answer:

   let low = 0, mid = 0, high = arr.length - 1; -> Option A

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 high to 0 instead of last index
• Starting mid at wrong position
• Using array length instead of length - 1

3. What will be the output of the following code snippet?

function dutchFlag(arr, pivot) {
  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) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    }
  }
  return arr;
}

console.log(dutchFlag([2, 5, 1, 2, 3, 2, 4], 2));

medium

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

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

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

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

Solution

1. Step 1: Trace swaps for elements less than pivot

   Elements less than 2 (which is 1) move to front; 1 swaps to index 0.

2. Step 2: Place all 2s in middle and greater elements at end

   All 2s stay in middle; 3,4,5 move to the right side in any order preserving partition.

3. Final Answer:

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

4. Quick Check:

   Partitioned array with less, equal, greater [OK]

Hint: Swap less than pivot left, greater right [OK]

Common Mistakes:

• Not swapping correctly when element equals pivot
• Mixing order of greater elements
• Forgetting to increment mid after swap with low

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

function partition(arr, pivot) {
  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) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    }
  }
  return arr;
}

medium

A. The pointers low and mid are initialized incorrectly

B. The while loop condition should be mid <= high, not mid < high

C. The swap operation is missing for elements equal to pivot

D. The high pointer should be incremented, not decremented

Solution

1. Step 1: Check loop condition correctness

   The loop must run while mid is less than or equal to high to process all elements.

2. Step 2: Identify impact of incorrect condition

   Using mid < high skips processing when mid equals high, missing last element check.

3. Final Answer:

   The while loop condition should be mid <= high, not mid < high -> Option B

4. Quick Check:

   Loop must cover all elements [OK]

Hint: Use mid <= high to cover all elements [OK]

Common Mistakes:

• Using mid < high causes last element to be skipped
• Incorrect pointer initialization
• Misunderstanding swap necessity for equal elements

5. Given an array [4, 9, 4, 7, 4, 8, 7] and pivot value 7, what will be the final array after applying the Dutch National Flag partition algorithm?

hard

A. [4, 4, 4, 7, 7, 8, 9]

B. [4, 4, 4, 7, 8, 7, 9]

C. [4, 4, 4, 7, 8, 9, 7]

D. [7, 7, 4, 4, 4, 8, 9]

Solution

1. Step 1: Partition elements less than pivot (7)

   All 4s move to the front: [4, 4, 4, ...]

2. Step 2: Place all 7s in the middle and greater elements at the end

   7s stay in the middle; 8 and 9 move to the right side in sorted order.

3. Final Answer:

   [4, 4, 4, 7, 7, 8, 9] -> Option A

4. Quick Check:

   Less, equal, greater partitioned correctly [OK]

Hint: Group less, equal, greater around pivot [OK]

Common Mistakes:

• Mixing order of greater elements
• Placing pivot elements incorrectly
• Not moving all less elements to front