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.