DSA problem
Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. The integers 0, 1, and 2 are used to represent the colors red, white, and blue respectively. You must solve this problem without using the library's sort function.
The naive approach is to call a built-in sort routine, which runs in O(n log n) time — but the problem explicitly forbids that. A simple counting-sort variant works in two passes: first count how many 0s, 1s, and 2s the array contains, then overwrite the array with those counts. That solution is O(n) time and O(1) space, but it scans the array twice and writes every cell.
The canonical optimal approach is the Dutch National Flag algorithm, invented by Edsger Dijkstra. It partitions the array into three regions in a single pass using three pointers: low marks the boundary just past the 0s, high marks the boundary just before the 2s, and mid scans the unprocessed middle region. The invariant is that everything left of low is 0, everything between low and mid is 1, and everything right of high is 2 — the segment [mid, high] is still unknown.
At each step we inspect nums[mid]. If it is 0, we swap it with nums[low] and advance both low and mid. If it is 1, it already belongs in the middle, so we just advance mid. If it is 2, we swap it with nums[high] and decrement high only (without advancing mid), because the value that came from high has not yet been classified. The loop ends when mid > high, at which point the three regions exactly cover the array. The whole sort runs in O(n) time, makes a single pass, and uses O(1) extra space.
Examples
nums = [2,0,2,1,1,0][0,0,1,1,2,2]nums = [2,0,1][0,1,2]nums = [0][0]Constraints
- n == nums.length
- 1 <= n <= 300
- nums[i] is either 0, 1, or 2.
- You must solve this problem without using the library's sort function.
- Could you come up with a one-pass algorithm using only constant extra space?
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.