Sort Colors
Last Updated: March 29, 2026
Understanding the Problem
At first, this might seem like a straightforward sorting problem. Just sort the array and you're done. But the problem explicitly says we can't use a library sort function, and the follow-up asks for a single-pass solution. That's a strong hint that there's something cleverer going on here.
The critical observation is that we only have three distinct values: 0, 1, and 2. We're not sorting arbitrary numbers. We're partitioning the array into exactly three groups. This is fundamentally different from general sorting, and it opens the door to linear-time algorithms that don't rely on comparisons between arbitrary elements.
This problem is also known as the Dutch National Flag Problem, first proposed by Edsger Dijkstra. The idea is to partition an array into three sections around a pivot value, which in our case is 1 (white). Everything less than the pivot goes left, everything equal stays in the middle, and everything greater goes right.
Key Constraints:
1 <= n <= 300— With n at most 300, even O(n^2) is blazingly fast. But the follow-up asks for a one-pass O(n) solution with O(1) space, so the real challenge is algorithmic elegance, not performance.nums[i]is either0,1, or2— Only three distinct values. This eliminates the need for general-purpose sorting. Counting or partitioning strategies become viable.in-place— We can't create a new array for the result. Any solution must rearrange elements within the original array.
Approach 1: Counting Sort (Two Pass)
Intuition
The simplest idea is to take advantage of the fact that there are only three possible values. Just count how many times each value appears, then overwrite the array with the right number of 0s, followed by 1s, followed by 2s.
This is essentially counting sort adapted for a tiny alphabet. It's hard to get wrong, and it's a solid starting point.
Algorithm
- Iterate through
numsand count the occurrences of 0, 1, and 2. - Overwrite
numswithcount0zeroes, thencount1ones, thencount2twos.
Example Walkthrough
Code
- Time Complexity: O(n). We make two passes through the array: one to count and one to overwrite. Each pass is O(n), so the total is O(n).
- Space Complexity: O(1). We only use three integer counters, regardless of the input size.
This approach works but requires two passes. Can we sort the array in a single pass by placing each element in its correct region as we encounter it?
Approach 2: Dutch National Flag (Three Pointers)
Intuition
This is the classic Dutch National Flag algorithm, designed by Dijkstra. The core idea is to maintain three regions in the array as we scan through it: everything before low is 0, everything between low and mid is 1, everything after high is 2, and everything between mid and high is unprocessed.
We use mid as our scanning pointer. If nums[mid] is 0, swap it with nums[low] and advance both. If it's 1, just advance mid. If it's 2, swap with nums[high] and shrink high, but don't advance mid because the swapped-in element hasn't been examined yet.
The algorithm maintains a key invariant: nums[0..low-1] contains only 0s, nums[low..mid-1] contains only 1s, nums[mid..high] is unprocessed, and nums[high+1..n-1] contains only 2s.
Each iteration processes one element from the unprocessed region. The reason mid advances when swapping with low but not with high is that the value at low is already processed (must be 1), so we can safely skip it. But the value at high could be anything and must be examined.
Algorithm
- Initialize
low = 0,mid = 0,high = n - 1. - While
mid <= high: - If
nums[mid] == 0: swapnums[mid]withnums[low], increment bothlowandmid. - If
nums[mid] == 1: incrementmid. - If
nums[mid] == 2: swapnums[mid]withnums[high], decrementhigh(don't incrementmid). - When the loop ends, the array is sorted.
Example Walkthrough
Code
- Time Complexity: O(n). Each iteration either increments
midor decrementshigh, so the total number of iterations is at most n. - Space Complexity: O(1). We only use three integer pointers, regardless of input size.