Sort Colors Two Pointer Dutch Flag in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the Dutch Flag sorting code?

Given the array [2, 0, 2, 1, 1, 0], what will be the state of the array after running the Dutch Flag sorting algorithm below?

DSA Javascript

function 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]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

console.log(sortColors([2, 0, 2, 1, 1, 0]));

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

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

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

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

💡 Hint

Think about how the pointers low, mid, and high move and swap elements.

The algorithm partitions the array into three parts: 0s at the start, 1s in the middle, and 2s at the end. It swaps elements to ensure this order.

🧠 Conceptual

intermediate

What is the role of the 'mid' pointer in the Dutch Flag algorithm?

In the Dutch Flag sorting algorithm, what does the 'mid' pointer represent during the sorting process?

A It scans through the array to classify elements as 0, 1, or 2.

B It points to the last sorted 2 in the array.

C It keeps track of the total number of swaps performed.

D It marks the boundary between sorted 0s and unsorted elements.

💡 Hint

Consider which pointer moves through the array checking each element.

The 'mid' pointer moves through the array from start to end, checking each element to decide if it should be swapped or skipped.

🔧 Debug

advanced

Identify the error in this Dutch Flag implementation

What error will this code produce when sorting colors using the Dutch Flag algorithm?

DSA Javascript

function 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]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

A The pointers low and mid are never incremented, causing an infinite loop.

B The swap syntax is invalid and causes a syntax error.

C The loop condition 'mid < high' causes some elements to be skipped, resulting in incorrect sorting.

D The function returns undefined because there is no return statement.

💡 Hint

Check the loop condition carefully and think about when the loop should stop.

The loop should run while mid <= high to ensure all elements are processed. Using mid < high skips the last element, causing incorrect sorting.

🚀 Application

advanced

How to modify Dutch Flag algorithm to sort an array with four colors?

If you have an array with four colors represented by 0, 1, 2, and 3, how can you extend the Dutch Flag algorithm to sort it efficiently?

A Modify the algorithm to use four pointers, each tracking one color's boundary.

B Run the Dutch Flag algorithm twice, first for 0,1,2 then for 1,2,3.

C Use a counting sort approach instead of the Dutch Flag algorithm.

D Use three pointers to partition the array into four parts, adjusting swaps accordingly.

💡 Hint

Think about how the original algorithm uses pointers to separate three groups.

By using three pointers, you can partition the array into four segments, moving elements to their correct positions in one pass.

❓ Predict Output

expert

What is the output after sorting with a modified Dutch Flag algorithm?

Given the array [1, 2, 0, 1, 2, 0, 1], what is the array state after running the code below?

DSA Javascript

function 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]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
  return nums;
}

console.log(sortColors([1, 2, 0, 1, 2, 0, 1]));

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

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

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

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

💡 Hint

Trace the swaps carefully, especially how 2s are moved to the end.

The algorithm moves all 0s to the front, 2s to the end, and leaves 1s in the middle, resulting in a sorted array.

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