Sort Colors Two Pointer Dutch Flag in DSA C#

Mental Model

We separate three groups of colors by moving pointers from left and right, swapping as needed to put all reds, whites, and blues in order.

Analogy: Imagine sorting three types of balls (red, white, blue) on a table by pushing reds to the left, blues to the right, and whites stay in the middle, using two hands moving inward.

Index:  0   1   2   3   4   5
Array: [2] [0] [2] [1] [1] [0]
Pointers:
low ↑          
high                 ↑
current ↑

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: current at index 0 is 2, swap with high at index 5 (0), decrement high

[0] [0] [2] [1] [1] [2]
low ↑
current ↑
high ↑

Why: 2 should be at the end, so swap with element at high pointer and move high left

Step 2: current at index 0 is 0, swap with low at index 0, increment low and current

[0] [0] [2] [1] [1] [2]
    low ↑
        current ↑
high ↑

Why: 0 should be at the start, so swap with low pointer and move both pointers right

Step 3: current at index 1 is 0, swap with low at index 1, increment low and current

[0] [0] [2] [1] [1] [2]
        low ↑
            current ↑
high ↑

Why: 0 should be at the start, so swap with low pointer and move both pointers right

Step 4: current at index 2 is 2, swap with high at index 4 (1), decrement high

[0] [0] [1] [1] [2] [2]
        low ↑
            current ↑
        high ↑

Why: 2 should be at the end, so swap with element at high pointer and move high left

Step 5: current at index 2 is 1, just move current forward

[0] [0] [1] [1] [2] [2]
        low ↑
                current ↑
        high ↑

Why: 1 is in the middle group, so just move current pointer right

Step 6: current at index 3 is 1, just move current forward

[0] [0] [1] [1] [2] [2]
        low ↑
                    current ↑
        high ↑

Why: 1 is in the middle group, so just move current pointer right

Result:

[0] [0] [1] [1] [2] [2]
Sorted array: 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Annotated Code

DSA C#

using System;

class SortColorsDutchFlag
{
    public static void SortColors(int[] nums)
    {
        int low = 0, current = 0, high = nums.Length - 1;
        while (current <= high)
        {
            if (nums[current] == 0)
            {
                // swap nums[current] and nums[low]
                int temp = nums[current];
                nums[current] = nums[low];
                nums[low] = temp;
                low++;
                current++;
            }
            else if (nums[current] == 2)
            {
                // swap nums[current] and nums[high]
                int temp = nums[current];
                nums[current] = nums[high];
                nums[high] = temp;
                high--;
                // do not increment current here
            }
            else
            {
                // nums[current] == 1, just move current
                current++;
            }
        }
    }

    public static void PrintArray(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            Console.Write(nums[i]);
            if (i != nums.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main()
    {
        int[] nums = {2, 0, 2, 1, 1, 0};
        SortColors(nums);
        PrintArray(nums);
    }
}

while (current <= high)

loop until current pointer passes high pointer

if (nums[current] == 0)

if current is 0, swap with low pointer and move both pointers right

swap nums[current] and nums[low]; low++; current++;

place 0 at start and advance pointers

else if (nums[current] == 2)

if current is 2, swap with high pointer and move high pointer left

swap nums[current] and nums[high]; high--;

place 2 at end, do not move current to recheck swapped value

else current++;

if current is 1, just move current pointer right

Output

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

Complexity Analysis

Time: O(n) because we scan the array once with pointers moving inward

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

vs Alternative: Compared to counting sort which uses extra space and two passes, this method sorts in one pass with constant space

Edge Cases

empty array

no operations, array remains empty

DSA C#

while (current <= high)

array with all same colors (e.g., all 0s)

pointers move through array without swaps, array stays same

DSA C#

if (nums[current] == 0)

array with only two colors (e.g., 0s and 1s)

swaps and pointer moves handle sorting correctly

DSA C#

else if (nums[current] == 2)

When to Use This Pattern

When you need to sort an array with exactly three distinct values efficiently, use the Dutch National Flag two-pointer pattern to sort in one pass.

Common Mistakes

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

Mistake: Swapping elements incorrectly or swapping with wrong pointers
Fix: Always swap 0 with low pointer and 2 with high pointer to maintain order

Summary

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

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

The key is to move 0s to the start and 2s to the end by swapping with low and high pointers.

Practice

1. What is the main idea behind the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. Swap elements randomly until sorted

B. Sort the array using built-in sort function

C. Count each color and then overwrite the array

D. Use three pointers to separate 0s, 1s, and 2s in one pass

Solution

1. Step 1: Understand the problem

   The algorithm sorts an array containing only 0s, 1s, and 2s representing colors.

2. Step 2: Use three pointers

   It uses three pointers: low, mid, and high to separate the colors in one pass efficiently.

3. Final Answer:

   Use three pointers to separate 0s, 1s, and 2s in one pass -> Option D

4. Quick Check:

   Three pointers = A [OK]

Hint: Remember three pointers separate colors in one pass [OK]

Common Mistakes:

• Using built-in sort instead of pointers
• Counting colors then rewriting array
• Swapping elements without pointers

2. Which of the following is the correct initialization of pointers in the Dutch Flag algorithm in C#?

easy

A. int low = 0, mid = 0, high = nums.Length - 1;

B. int low = nums.Length - 1, mid = 0, high = 0;

C. int low = 0, mid = nums.Length - 1, high = 0;

D. int low = 0, mid = 1, high = nums.Length;

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high starts at last index (length - 1).

2. Step 2: Check initialization correctness

   int low = 0, mid = 0, high = nums.Length - 1; correctly sets low and mid to 0, high to nums.Length - 1.

3. Final Answer:

   int low = 0, mid = 0, high = nums.Length - 1; -> Option A

4. Quick Check:

   Correct pointer init = C [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 length - 1
• Using invalid pointer values

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

medium

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

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

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

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

Solution

1. Step 1: Start with pointers low=0, mid=0, high=5

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

2. Step 2: Process elements using Dutch Flag logic

   Swap 2 with 0 at high, move high left; swap 2 with 0 at low; move mid and low accordingly until sorted.

3. Final Answer:

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

4. Quick Check:

   Sorted colors = A [OK]

Hint: Swap 0s left, 2s right, 1s stay middle [OK]

Common Mistakes:

• Not swapping correctly
• Moving pointers incorrectly
• Confusing order of colors

4. Identify the bug in the following C# code snippet for the Dutch Flag algorithm:

int low = 0, mid = 0, high = nums.Length - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    Swap(nums, low, mid);
    low++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    Swap(nums, mid, high);
    high--;
  }
}

medium

A. Swap function parameters are incorrect

B. Missing increment of mid after swapping 0

C. high should be incremented instead of decremented

D. mid should not be incremented when nums[mid] == 1

Solution

1. Step 1: Check pointer increments after swaps

   When nums[mid] == 0, after swapping with low, mid must also increment to avoid infinite loop.

2. Step 2: Identify missing mid++

   The code increments low but misses mid++, causing mid to stay and loop endlessly.

3. Final Answer:

   Missing increment of mid after swapping 0 -> Option B

4. Quick Check:

   Increment mid after 0 swap = D [OK]

Hint: Always increment mid after swapping 0 [OK]

Common Mistakes:

• Forgetting mid++ after swapping 0
• Decrementing high incorrectly
• Incorrect swap parameters

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch Flag algorithm to sort an array that also contains 3s, placing all 3s at the end?

hard

A. Add a fourth pointer and extend the logic to handle 3s at the end

B. Use the same three pointers but treat 3s as 2s

C. Sort the array normally using built-in sort for 3s

D. Ignore 3s since they are already at the end

Solution

1. Step 1: Understand limitation of three pointers

   The original algorithm handles only three values (0,1,2). Adding 3 requires extra handling.

2. Step 2: Introduce a fourth pointer

   Use four pointers to separate 0s, 1s, 2s, and 3s, extending the logic to place 3s at the end.

3. Final Answer:

   Add a fourth pointer and extend the logic to handle 3s at the end -> Option A

4. Quick Check:

   Four pointers for four colors = B [OK]

Hint: Add pointer per unique value for correct sorting [OK]

Common Mistakes:

• Treating 3s as 2s causing wrong order
• Using built-in sort instead of pointers
• Ignoring 3s placement