Sort Colors
Understanding the Problem
Sorting the array with a comparison sort would produce the right answer, but the problem forbids the library sort function and the follow-up asks for a single pass. Both point toward an algorithm that uses a property general sorting cannot.
The array holds only three distinct values: 0, 1, and 2. We are not ordering arbitrary numbers, we are partitioning the array into three groups. That difference allows linear-time algorithms that never compare two arbitrary elements.
This is the Dutch National Flag Problem, posed by Edsger Dijkstra. It partitions an array into three sections around a pivot value, which here is 1 (white). Everything less than the pivot goes left, everything equal stays in the middle, and everything greater goes right.
Key Constraints:
nums[i]is either0,1, or2. Three distinct values mean we can count or partition instead of running a general-purpose sort.in-place: we cannot allocate a separate result array. Any solution must rearrange elements withinnumsitself.1 <= n <= 300: small enough that performance is not the deciding factor. The follow-up, a single O(n) pass in O(1) space, is what shapes the target solution.
Approach 1: Counting Sort (Two Pass)
Intuition
With only three possible values, we can count how many times each one appears, then overwrite the array with that many 0s, followed by that many 1s, followed by that many 2s. Since the sorted array is the three groups laid out in order, the counts alone determine the result.
This is counting sort restricted to an alphabet of size three.
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 solution reads the array twice. The next approach answers the follow-up by sorting in a single pass, placing each element into its final region the moment it is examined.
Approach 2: Dutch National Flag (Three Pointers)
Intuition
The Dutch National Flag algorithm maintains three regions while scanning the array once. Everything before low is 0, everything from low up to mid is 1, everything after high is 2, and everything from mid through high is still unprocessed.
mid is the scanning pointer. If nums[mid] is 0, swap it into the 0-region with nums[low] and advance both pointers. If it is 1, advance mid since 1 belongs in the middle region. If it is 2, swap it into the 2-region with nums[high] and decrement high, without advancing mid, because the element swapped in from high has not been examined yet.
The loop preserves four invariants: nums[0..low-1] holds only 0s, nums[low..mid-1] holds only 1s, nums[mid..high] is unprocessed, and nums[high+1..n-1] holds only 2s.
The asymmetry in pointer movement follows from these invariants. When nums[mid] is 0, the swap brings up the value at low, which by the invariant is a 1 (the only other possibility, low == mid, makes it a self-swap). Either way the element now at mid is settled, so mid can advance. When nums[mid] is 2, the swap brings up the value at high, which came from the unprocessed region and could be 0, 1, or 2, so mid must stay and re-examine it.
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.