Sort Colors: Dutch National Flag Pattern

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.

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

Complexity

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