Sort Colors Two Pointer Dutch Flag in DSA Python

Mental Model

We use three pointers to separate the array into three parts by swapping colors in one pass.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls between boxes with two hands.

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

Dry Run Walkthrough

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

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

Step 1: mid points to 2, swap with high (0), decrease high

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

Why: 2 should be at the end, so swap it with the element at high and reduce high

Step 2: mid points to 0, swap with low (2), increase low and mid

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

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

Step 3: mid points to 2, swap with high (0), decrease high

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

Why: 2 should be at the end, swap with high and reduce high

Step 4: mid points to 0, swap with low (0), increase low and mid

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

Why: 0 should be at the start, swap with low and move pointers forward

Step 5: mid points to 1, just move mid forward

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

Why: 1 is in the middle, just move mid forward

Step 6: mid points to 1, just move mid forward

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

Why: 1 is in the middle, just move mid forward

Result:

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

Annotated Code

DSA Python

class Solution:
    def sortColors(self, nums):
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1


if __name__ == '__main__':
    arr = [2, 0, 2, 1, 1, 0, 0]
    Solution().sortColors(arr)
    print(' -> '.join(map(str, arr)) + ' -> null')

while mid <= high:

continue until mid passes high to process all elements

if nums[mid] == 0:

if current is 0, swap with low and move low and mid forward

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

swap 0 to the front

low += 1 mid += 1

advance low and mid pointers after placing 0

elif nums[mid] == 1:

if current is 1, just move mid forward

mid += 1

advance mid pointer to check next element

else: # nums[mid] == 2

if current is 2, swap with high and move high backward

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

swap 2 to the end

high -= 1

decrease high pointer after placing 2

Output

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

Complexity Analysis

Time: O(n) because we traverse 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 and two passes, this method is faster and uses constant space

Edge Cases

empty array

function returns immediately without error

DSA Python

while mid <= high:

array with all same colors

array remains unchanged after processing

DSA Python

while mid <= high:

array with only two colors

colors are sorted correctly with same logic

DSA Python

while mid <= high:

When to Use This Pattern

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

Common Mistakes

Mistake: Moving mid pointer forward after swapping with high when nums[mid] == 2
Fix: Do not move mid forward after swapping with high because the swapped element needs to be checked

Mistake: Swapping without updating pointers correctly
Fix: Update low and mid after swapping 0, and update high after swapping 2 properly

Summary

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

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

The key is to move 0s to the front and 2s to the end by swapping and adjusting pointers carefully.

Practice

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

easy

A. To reverse the elements of an array

B. To sort any array of integers in ascending order

C. To find the maximum element in 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 algorithm's purpose

   It sorts these values in one pass using two pointers, placing all 0s first, then 1s, then 2s.

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 array, not just 0,1,2
• Confusing it with general sorting algorithms
• Assuming it requires multiple passes

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

easy

A. low, mid, high = 0, len(nums) - 1, 0

B. low, mid, high = 0, 0, len(nums) - 1

C. low, mid, high = len(nums) - 1, 0, 0

D. low, mid, high = len(nums) - 1, len(nums) - 1, 0

Solution

1. Step 1: Recall pointer roles

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

2. Step 2: Match initialization

   So, low = 0, mid = 0, high = len(nums) - 1 is correct.

3. Final Answer:

   low, mid, high = 0, 0, len(nums) - 1 -> Option B

4. Quick Check:

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

Hint: Start low and mid at 0, high at last index [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 of the following code snippet?

nums = [2, 0, 2, 1, 1, 0]
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

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, 1, 0, 2, 2]

Solution

1. Step 1: Trace the algorithm on input

   Initially nums = [2,0,2,1,1,0]. The algorithm swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After the loop, nums becomes [0,0,1,1,2,2], sorted by color.

3. Final Answer:

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

4. Quick Check:

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

Hint: Remember: 0s front, 1s middle, 2s end [OK]

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing order of pointers

4. Identify the bug in the following Dutch Flag algorithm code:

nums = [2, 0, 1]
low, mid, high = 0, 0, len(nums) - 1
while mid < high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

medium

A. The loop condition should be 'mid <= high' instead of 'mid < high'

B. Pointers low and mid are initialized incorrectly

C. Swapping logic for nums[mid] == 0 is wrong

D. The decrement of high should be after incrementing mid

Solution

1. Step 1: Analyze loop condition

   The loop runs while mid < high, so it stops when mid == high, missing last element check.

2. Step 2: Correct loop condition

   It should be mid <= high to process all elements including when mid equals high.

3. Final Answer:

   The loop condition should be 'mid <= high' instead of 'mid < high' -> Option A

4. Quick Check:

   Loop must cover mid == high [OK]

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

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pointer initialization unnecessarily
• Incorrect swap logic for 0 or 2

5. Given an array nums = [1, 2, 0, 1, 2, 0, 1], how many swaps will the Dutch Flag algorithm perform to sort it?

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace swaps during sorting

   Initial: [1,2,0,1,2,0,1] low=0, mid=0, high=6
   - mid=0 (1): mid=1 (no swap)
   - mid=1 (2): swap(1,6) -> [1,1,0,1,2,0,2] high=5 (swap 1)
   - mid=1 (1): mid=2
   - mid=2 (0): swap(0,2) -> [0,1,1,1,2,0,2] low=1 mid=3 (swap 2)
   - mid=3 (1): mid=4
   - mid=4 (2): swap(4,5) -> [0,1,1,1,0,2,2] high=4 (swap 3)
   - mid=4 (0): swap(1,4) -> [0,0,1,1,1,2,2] low=2 mid=5 (swap 4)

2. Step 2: Total swaps counted

   There are 4 swaps in total during the process.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 moves happen [OK]

Common Mistakes:

• Counting pointer moves as swaps
• Missing swaps when swapping with same element
• Not tracing all pointer changes