Sort Colors Two Pointer Dutch Flag in DSA Javascript

Mental Model

We use three pointers to separate the array into three parts: zeros, ones, and twos. We swap elements to put them in the right part without extra space.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls between boxes using just your hands, without extra containers.

Index:  0  1  2  3  4  5
Array: [2] -> [0] -> [2] -> [1] -> [1] -> [0]
Pointers:
low ↑ mid ↑                   high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0]

Goal: Sort the array so that all 0s come first, then 1s, then 2s

Step 1: swap element at mid=0 (2) with element at high=5 (0), then decrease high to 4

[0] -> [0] -> [2] -> [1] -> [1] -> [2]
low ↑ mid ↑                   high ↓

Why: We move 2s to the end by swapping with high pointer and reduce the high boundary. Do not increment mid yet as new element at mid needs checking.

Step 2: swap element at low=0 (0) with element at mid=0 (0) (no-op), then increase low to 1 and mid to 1

[0] -> [0] -> [2] -> [1] -> [1] -> [2]
     low ↑ mid ↑               high ↓

Why: We move 0s to the front by swapping with low pointer and move both pointers forward

Step 3: increment mid because element at mid=1 (0) is 0, swap with low=1 (0) no-op, then increase low to 2 and mid to 2

[0] -> [0] -> [2] -> [1] -> [1] -> [2]
       low ↑   mid ↑         high ↓

Why: We move 0s to the front by swapping with low pointer and move both pointers forward

Step 4: swap element at mid=2 (2) with element at high=4 (1), then decrease high to 3

[0] -> [0] -> [1] -> [1] -> [2] -> [2]
       low ↑ mid ↑       high ↓

Why: We move 2s to the end by swapping with high pointer and reduce the high boundary

Step 5: increment mid because element at mid=2 (now 1) is 1

[0] -> [0] -> [1] -> [1] -> [2] -> [2]
       low ↑     mid ↑   high ↓

Why: We skip 1s and move mid forward to process next element

Step 6: increment mid because element at mid=3 (1) is 1, mid=4 > high=3, done

[0] -> [0] -> [1] -> [1] -> [2] -> [2]
       low ↑         mid ↑ high ↓

Why: We skip 1s and move mid forward, loop ends

Result:

[0] -> [0] -> [1] -> [1] -> [2] -> [2]

Annotated Code

DSA Javascript

class Solution {
  sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
      if (nums[mid] === 0) {
        [nums[low], nums[mid]] = [nums[mid], nums[low]]; // swap 0 to front
        low++;
        mid++;
      } else if (nums[mid] === 1) {
        mid++; // skip 1
      } else { // nums[mid] === 2
        [nums[mid], nums[high]] = [nums[high], nums[mid]]; // swap 2 to end
        high--;
      }
    }
  }
}

// Driver code
const arr = [2, 0, 2, 1, 1, 0];
const sol = new Solution();
sol.sortColors(arr);
console.log(arr.join(' -> '));

while (mid <= high) {

continue processing until mid passes high boundary

if (nums[mid] === 0) {

found 0, swap it to the front section

[nums[low], nums[mid]] = [nums[mid], nums[low]];

swap current mid element with low pointer element

low++; mid++;

advance low and mid pointers after placing 0

else if (nums[mid] === 1) {

found 1, just move mid forward

mid++;

skip 1 by advancing mid

else {

found 2, swap it to the end section

[nums[mid], nums[high]] = [nums[high], nums[mid]];

swap current mid element with high pointer element

high--;

reduce high boundary after placing 2

Output

0 -> 0 -> 1 -> 1 -> 2 -> 2

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer

Space: O(1) because sorting is done in place without extra space

vs Alternative: Compared to counting sort which uses extra space, this uses constant space and one pass

Edge Cases

empty array

no operations, array remains empty

DSA Javascript

while (mid <= high) {

array with all zeros

all elements remain in place, low and mid move through entire array

DSA Javascript

if (nums[mid] === 0) {

array with all twos

all elements swapped to end, high moves to front

DSA Javascript

else {

When to Use This Pattern

When you need to sort an array with only three distinct values efficiently, use the Dutch National Flag pattern with two or three pointers to partition in one pass.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high when nums[mid] is 2
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping incorrectly or mixing up low and mid pointers
Fix: Always swap nums[mid] with nums[low] when nums[mid] is 0, and swap nums[mid] with nums[high] when nums[mid] is 2

Summary

Sorts an array of 0s, 1s, and 2s in one pass using three pointers.

Use when you have exactly three distinct values to sort efficiently without extra space.

The key is to maintain boundaries for 0s, 1s, and 2s and swap elements into correct partitions while scanning once.

Practice

1. What is the main goal of the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. To find the maximum value in an array

B. To sort any array of integers in ascending order

C. To reverse the elements of an array

D. To sort an array containing only 0s, 1s, and 2s in a single pass

Solution

1. Step 1: Understand the problem context

   The algorithm is designed specifically for arrays with only three distinct values: 0, 1, and 2.

2. Step 2: Identify the sorting goal

   The goal is to sort these values so that all 0s come first, then all 1s, and finally all 2s, in one pass without extra space.

3. Final Answer:

   To sort an array containing only 0s, 1s, and 2s in a single pass -> Option D

4. Quick Check:

   Sort Colors = Sort 0,1,2 in one pass [OK]

Hint: Remember: Dutch Flag sorts 0,1,2 in one pass [OK]

Common Mistakes:

• Thinking it sorts any integer array
• Confusing it with general sorting algorithms
• Assuming it reverses the array

2. Which of the following is the correct initialization for the two pointers in the Dutch Flag algorithm in JavaScript?

easy

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

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

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

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

Solution

1. Step 1: Identify pointer roles

   Low and mid start at the beginning (index 0), high starts at the end (last index).

2. Step 2: Match initialization to roles

   Correct initialization is let low = 0, mid = 0, high = nums.length - 1;.

3. Final Answer:

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

4. Quick Check:

   Pointers start low=0, mid=0, high=end [OK]

Hint: Start low and mid at 0, high at array end [OK]

Common Mistakes:

• Swapping high and mid initialization
• Starting pointers at wrong indices
• Using length instead of length - 1 for high

3. What will be the output array after running the Dutch Flag algorithm on nums = [2, 0, 2, 1, 1, 0]?

medium

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

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

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

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

Solution

1. Step 1: Apply Dutch Flag sorting logic

   Sort 0s to front, 1s in middle, 2s at end in one pass.

2. Step 2: Result after sorting

   The sorted array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

   Sorted colors = 0s, then 1s, then 2s [OK]

Hint: Sort 0s front, 1s middle, 2s end in one pass [OK]

Common Mistakes:

• Not sorting all 0s to front
• Mixing order of 1s and 2s
• Returning original unsorted array

4. Identify the bug in this snippet of the Dutch Flag algorithm:

let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
  if (nums[mid] === 0) {
    [nums[low], nums[mid]] = [nums[mid], nums[low]];
    low++;
  } else if (nums[mid] === 2) {
    [nums[mid], nums[high]] = [nums[high], nums[mid]];
    high--;
  } else {
    mid++;
  }
}

medium

A. Incorrect comparison operator in while loop

B. Missing increment of mid after swapping 0s

C. Swapping 2s with low instead of high

D. No bug, code is correct

Solution

1. Step 1: Analyze pointer increments after swaps

   When swapping 0s, mid pointer must also move forward to avoid infinite loop.

2. Step 2: Identify missing mid++ after swapping 0s

   The code increments low but forgets to increment mid after swapping 0s.

3. Final Answer:

   Missing increment of mid after swapping 0s -> Option B

4. Quick Check:

   mid++ missing after 0 swap causes infinite loop [OK]

Hint: Increment mid after swapping 0s to avoid infinite loop [OK]

Common Mistakes:

• Forgetting mid++ after swapping 0s
• Swapping 2s with wrong pointer
• Incorrect loop condition

5. Given an array nums with values 0, 1, and 2, how would you modify the Dutch Flag algorithm to count how many swaps are performed during sorting?

hard

A. Use a separate array to track swaps

B. Count the number of 0s, 1s, and 2s before sorting

C. Add a counter variable and increment it each time a swap occurs

D. Increment a counter only when mid pointer moves

Solution

1. Step 1: Understand swap operations in algorithm

   Swaps happen when 0 or 2 is encountered and elements are exchanged.

2. Step 2: Track swaps with a counter

   Introduce a variable initialized to zero and increment it every time a swap line executes.

3. Final Answer:

   Add a counter variable and increment it each time a swap occurs -> Option C

4. Quick Check:

   Count swaps by incrementing counter on each swap [OK]

Hint: Increment counter inside swap blocks to count swaps [OK]

Common Mistakes:

• Counting pointer moves instead of swaps
• Counting elements instead of swaps
• Using extra arrays unnecessarily