Sort Colors Solution

Problem

Given an array where every element is 0, 1, or 2 (representing red, white, and blue), sort it in-place so all 0s appear first, then all 1s, then all 2s — without using any built-in sort function.

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: The three colors are grouped in order — reds, then whites, then blues.

Counter-example: [0, 1, 2, 0, 1, 2] is not sorted because the second group of 0s and 1s is out of place.

Intuition

Because the values are restricted to exactly 0, 1, and 2, a general-purpose sort is unnecessary overkill. Think of the array as three regions growing inward from both ends: a "confirmed 0" section on the left, a "confirmed 2" section on the right, and an unsorted middle in between. A single pointer sweeps through that middle, and each element it encounters either gets placed into the left region, stays in place, or gets placed into the right region — until the sweep meets the right boundary and the middle vanishes.

Solution — Dutch National Flag

Maintain three pointers: low marks the next slot for a 0, mid is the current element being inspected, and high marks the next slot for a 2. When mid finds a 0, swap it left and advance both low and mid (the element from low was definitely a 1, so it's safe to advance). When mid finds a 2, swap it right and shrink high — but do not advance mid, because the element swapped in from high is unknown. When mid finds a 1, just advance mid.

Initialize low = 0, mid = 0, high = len(nums) - 1.
Loop while mid <= high.
If nums[mid] == 0: swap nums[low] and nums[mid], increment both low and mid.
If nums[mid] == 1: increment mid only.
If nums[mid] == 2: swap nums[mid] and nums[high], decrement high only.
When the loop ends, the array is sorted in-place.

1def sortColors(nums: list[int]) -> None:
2    low, mid, high = 0, 0, len(nums) - 1
3
4    while mid <= high:
5        if nums[mid] == 0:
6            nums[low], nums[mid] = nums[mid], nums[low]
7            low += 1
8            mid += 1  # element swapped from low was a 1, already inspected
9        elif nums[mid] == 1:
10            mid += 1
11        else:
12            nums[mid], nums[high] = nums[high], nums[mid]
13            high -= 1  # don't advance mid — swapped element is unseen

Time: O(n) — each element is visited at most once; mid only advances or high only retreats, so the total number of steps is bounded by n.

Space: O(1) — the three pointers are the only extra memory; sorting is done entirely in-place.

Complexity Summary

Approach	Time	Space	When to use
Dutch National Flag (3 pointers)	O(n)	O(1)	Any time you need a single-pass, in-place sort over exactly three distinct values

Common Mistakes

Not advancing mid after a 0-swap, or advancing it after a 2-swap — when you swap a 2 to the right, the element that came back from high is unknown; mid must stay put. When you swap a 0 to the left, the element that was at low had already been inspected (it was a 1), so advancing mid is safe.
Using mid < high as the loop condition — when mid == high, there is still one uninspected element; the correct condition is mid <= high.
Swapping nums[mid] with nums[high] and then immediately decrementing both high and mid — mid must not move after a 2-swap; the swapped-in element could be 0, 1, or 2 and needs a fresh check.
Reaching for a comparison sort — O(n log n) is unnecessary here; the fixed domain of three values makes a linear pass possible, and interviewers specifically expect the constant-space single-pass solution.
Forgetting the edge case of an all-same-value array — the algorithm handles it correctly (pointers never cross), but it's easy to forget to test it mentally when tracing examples.

Sort Colors — Solution

Problem

Intuition

Solution — Dutch National Flag

Complexity Summary

Common Mistakes

Related Problems

Ready to practice? Try it on SkillFlow