Sort Colors Dutch National Flag DSA Solution

Learning Outcome

After this lesson, you should be able to maintain three zones and sort 0s, 1s, and 2s in one pass.

Problem Statement

Given an array containing only 0, 1, and 2, sort it in-place so equal colors are grouped together.

Input	Output	Why
`nums = [2,0,2,1,1,0]`	`[0,0,1,1,2,2]`	All 0s move left, 1s stay in the middle, and 2s move right.

Brute Force Approach

Count the number of 0s, 1s, and 2s, then overwrite the array. This is valid, but it takes two passes.

Optimized Approach

Use three pointers: low for the next 0 position, mid for the current unknown, and high for the next 2 position.

Exact Pseudocode

low = 0
mid = 0
high = n - 1
while mid <= high:
  if nums[mid] == 0:
    swap nums[low], nums[mid]
    low += 1
    mid += 1
  else if nums[mid] == 1:
    mid += 1
  else:
    swap nums[mid], nums[high]
    high -= 1

Reference Code

class Solution:
    def sortColors(self, nums):
        low = 0
        mid = 0
        high = 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

Sample Dry Run

Step	State	Result
Start	low=0, mid=0, high=5	unknown zone is full array
nums[mid]=2	Swap mid with high	2 moves right; do not increment mid
nums[mid]=0	Swap low with mid	0 moves left; low and mid move
Finish	mid passes high	array is sorted

Complexity

Measure	Value	Reason
Time	O(n)	Each element is moved into its zone with one scan.
Space	O(1)	Only three pointers are used.

Edge Cases

After swapping a 2 with high, do not increment mid.
Arrays with all same values should still work.
Empty or single-element arrays are already sorted.

Interview Checklist

Maintain zones: 0s before low, 1s before mid, 2s after high.
Increment mid only after resolving a 0 or 1.
Keep the algorithm in-place.

FAQs

Why not increment mid after swapping a 2?

The value swapped from high has not been processed yet, so mid must inspect it.

Why is this one pass?

mid scans the unknown zone once while low and high shrink the boundaries.

What is the core pattern?

Dutch National Flag three-pointer partitioning.

Sort Colors: Dutch National Flag Pattern