Sort Colors
LeetCode #75 · Medium · Two Pointers · C++ solution with worked-out approach and complexity analysis.
Approach
Counting Sort (Two-pass)
Key insight
Since we only have three distinct values (0, 1, 2), we can count the occurrences of each and then overwrite the array.
Strategy
- 1First pass: Count occurrences of 0s (red), 1s (white), and 2s (blue)
- 2Second pass: Overwrite the array based on counts
Time
O(n)
two passes through the array
Space
O(1)
only three counter variables
Problem description(from LeetCode)
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. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.
Examples
Example 1
- Input:
- nums = [2,0,2,1,1,0]
- Output:
- [0,0,1,1,2,2]
Constraints
- •n == nums.length
- •1 <= n <= 300
- •nums[i] is either 0, 1, or 2.
Follow-up
Could you come up with a one-pass algorithm using only constant extra space?
C++ Solution
solution.cpp
class Solution {
public:
void sortColors(vector<int> &nums) {
int redCount = 0, whiteCount = 0, blueCount = 0;
for (int num : nums) {
redCount += (num == 0);
whiteCount += (num == 1);
blueCount += (num == 2);
}
for (int i = 0, n = nums.size(); i < n; i++) {
nums[i] = (redCount--) > 0 ? 0 : ((whiteCount--) > 0 ? 1 : 2);
}
}
/*
* Approach 2: Dutch National Flag Algorithm (One-pass) - Follow-up Solution
*
* Key Insight: Use three pointers to partition the array in a single pass.
* This is the famous algorithm by Edsger Dijkstra.
*
* Strategy:
* - low: boundary for 0s (all elements before low are 0)
* - mid: current element being examined
* - high: boundary for 2s (all elements after high are 2)
*
* Invariants maintained:
* - [0, low): all 0s (red)
* - [low, mid): all 1s (white)
* - [mid, high]: unprocessed elements
* - (high, n): all 2s (blue)
*
* Process:
* - If nums[mid] == 0: swap with nums[low], increment both low and mid
* - If nums[mid] == 1: just increment mid (it's in the right place)
* - If nums[mid] == 2: swap with nums[high], decrement high (don't increment
* mid because the swapped element needs to be examined)
*
* Time Complexity: O(n) - single pass through the array
* Space Complexity: O(1) - only three pointer variables
*/
void sortColorsOnePass(vector<int> &nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else { // nums[mid] == 2
swap(nums[mid], nums[high]);
high--;
// Don't increment mid, need to examine the swapped element
}
}
}
};