18. Sort Colors
🔗 LeetCode Problem: 75. Sort Colors
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers, Sorting
Problem Statement
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.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,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 space?
🎨 Visual Understanding
The Problem Visualized
Input: [2, 0, 2, 1, 1, 0]
Colors:
0 = Red
1 = White
2 = Blue
Goal: Sort so all reds together, all whites together, all blues together
[Red, Red, White, White, Blue, Blue]
[0, 0, 1, 1, 2, 2]
Result: [0, 0, 1, 1, 2, 2]
Why This is Called "Dutch National Flag Problem"
Dutch flag has three horizontal stripes:
┌──────────────┐
│ Red (0) │
├──────────────┤
│ White (1) │
├──────────────┤
│ Blue (2) │
└──────────────┘
Problem: Partition array into three sections
Similar to partitioning the flag!
Different Approaches
Approach 1: Built-in Sort
Arrays.sort(nums);
Time: O(n log n)
✗ Not optimal, violates "don't use library sort"
Approach 2: Counting Sort (Two Pass)
Count 0s, 1s, 2s → Overwrite array
Time: O(n), but two passes
✓ Good, but can we do better?
Approach 3: Dutch National Flag (One Pass)
Three pointers: low, mid, high
Partition in single pass
Time: O(n), one pass
✓ Optimal!
🎯 Approach 1: Counting Sort (Two Pass)
The Most Natural Thinking 💭
Core Logic:
Count each color, then reconstruct array:
Pass 1: Count occurrences
count0 = number of 0s
count1 = number of 1s
count2 = number of 2s
Pass 2: Overwrite array
Fill first count0 positions with 0
Fill next count1 positions with 1
Fill last count2 positions with 2
Why This Works: - Simple counting approach - Guaranteed to place colors in order - O(n) time complexity
Trade-off: - Two passes through array - Follow-up asks for one-pass - Still good solution though
Implementation
public void sortColors(int[] nums) {
// Pass 1: Count each color
int count0 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == 0) count0++;
else if (num == 1) count1++;
else count2++;
}
// Pass 2: Overwrite array
int index = 0;
// Fill 0s
for (int i = 0; i < count0; i++) {
nums[index++] = 0;
}
// Fill 1s
for (int i = 0; i < count1; i++) {
nums[index++] = 1;
}
// Fill 2s
for (int i = 0; i < count2; i++) {
nums[index++] = 2;
}
}
Step-by-Step Execution: nums = [2,0,2,1,1,0]
Pass 1: Count each color
═══════════════════════════════════════════════════════════════════
Scan [2, 0, 2, 1, 1, 0]:
2 → count2++
0 → count0++
2 → count2++
1 → count1++
1 → count1++
0 → count0++
Result: count0=2, count1=2, count2=2
Pass 2: Overwrite array
═══════════════════════════════════════════════════════════════════
Fill 0s (count0=2):
nums[0] = 0
nums[1] = 0
nums = [0, 0, 2, 1, 1, 0]
Fill 1s (count1=2):
nums[2] = 1
nums[3] = 1
nums = [0, 0, 1, 1, 1, 0]
Fill 2s (count2=2):
nums[4] = 2
nums[5] = 2
nums = [0, 0, 1, 1, 2, 2]
═══════════════════════════════════════════════════════════════════
🎯 RESULT: [0, 0, 1, 1, 2, 2]
═══════════════════════════════════════════════════════════════════
⏰ Time: O(n) - two passes
💾 Space: O(1) - only counters
✅ Approach 2: Dutch National Flag (One Pass - Optimal)
The Breakthrough Insight 💡
Core Logic:
Use three pointers to partition array in ONE pass:
low: boundary for 0s (everything before low is 0)
mid: current element being examined
high: boundary for 2s (everything after high is 2)
Initial state: low=0, mid=0, high=n-1
Array visualization:
[0s | unknowns | 2s]
low mid high
Strategy:
- If nums[mid] == 0 → swap with low, move both low and mid
- If nums[mid] == 1 → just move mid (1s stay in middle)
- If nums[mid] == 2 → swap with high, move only high
Three Regions:
Before: [2, 0, 2, 1, 1, 0]
low,mid high
Goal: Create three regions
[0, 0, 0 | 1, 1, 1 | 2, 2, 2]
← low mid → high →
Rules:
- [0...low): all 0s
- [low...mid): all 1s
- [mid...high]: unknown (being processed)
- (high...n): all 2s
Why This is Better: - Single pass through array - O(n) time with one pass (optimal!) - O(1) space - Elegant partitioning algorithm - Industry standard solution
Implementation
public void sortColors(int[] nums) {
int low = 0; // Boundary for 0s
int mid = 0; // Current element
int high = nums.length - 1; // Boundary for 2s
while (mid <= high) {
if (nums[mid] == 0) {
// Found 0, swap to low region
swap(nums, low, mid);
low++;
mid++;
} else if (nums[mid] == 1) {
// Found 1, already in correct region
mid++;
} else { // nums[mid] == 2
// Found 2, swap to high region
swap(nums, mid, high);
high--;
// Don't increment mid (need to check swapped element)
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Step-by-Step Execution: nums = [2,0,2,1,1,0]
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [2, 0, 2, 1, 1, 0]
↑ ↑
low,mid high
Regions: [unknown | unknown | unknown]
Iteration 1: mid=0, nums[mid]=2
═══════════════════════════════════════════════════════════════════
nums[mid]=2 → swap with high
swap(nums[0], nums[5]): [0, 0, 2, 1, 1, 2]
high-- → high=4
mid stays at 0 (need to check swapped element)
nums = [0, 0, 2, 1, 1, 2]
↑ ↑
low,mid high
Iteration 2: mid=0, nums[mid]=0
═══════════════════════════════════════════════════════════════════
nums[mid]=0 → swap with low
swap(nums[0], nums[0]): [0, 0, 2, 1, 1, 2] (no change)
low++ → low=1
mid++ → mid=1
nums = [0, 0, 2, 1, 1, 2]
↑ ↑
low mid
high
Iteration 3: mid=1, nums[mid]=0
═══════════════════════════════════════════════════════════════════
nums[mid]=0 → swap with low
swap(nums[1], nums[1]): [0, 0, 2, 1, 1, 2] (no change)
low++ → low=2
mid++ → mid=2
nums = [0, 0, 2, 1, 1, 2]
↑ ↑
low,mid
high
Iteration 4: mid=2, nums[mid]=2
═══════════════════════════════════════════════════════════════════
nums[mid]=2 → swap with high
swap(nums[2], nums[4]): [0, 0, 1, 1, 2, 2]
high-- → high=3
mid stays at 2
nums = [0, 0, 1, 1, 2, 2]
↑ ↑
low,mid
high
Iteration 5: mid=2, nums[mid]=1
═══════════════════════════════════════════════════════════════════
nums[mid]=1 → just move mid
mid++ → mid=3
nums = [0, 0, 1, 1, 2, 2]
↑ ↑
low mid,high
Iteration 6: mid=3, nums[mid]=1
═══════════════════════════════════════════════════════════════════
nums[mid]=1 → just move mid
mid++ → mid=4
nums = [0, 0, 1, 1, 2, 2]
↑ ↑
low mid
high
mid > high → Stop
Final State:
═══════════════════════════════════════════════════════════════════
nums = [0, 0, 1, 1, 2, 2]
[0s| 1s | 2s]
Sorted! ✓
Visual Representation of Regions
Start: [2, 0, 2, 1, 1, 0]
[?????????]
low,mid high
After some iterations: [0, 0, 1, 1, ?, 2]
[0s|1s|?|2s]
low mid high
End: [0, 0, 1, 1, 2, 2]
[0s| 1s | 2s]
low mid
high
⏰ Time: O(n) - single pass
💾 Space: O(1) - only three pointers
🔍 Edge Cases
Case 1: Already sorted
Input: [0,1,2]
Output: [0,1,2]
Strategy: Algorithm handles efficiently
Case 2: Reverse sorted
Input: [2,1,0]
Output: [0,1,2]
Case 3: All same color (all 0s)
Input: [0,0,0]
Output: [0,0,0]
Case 4: All same color (all 1s)
Input: [1,1,1]
Output: [1,1,1]
Case 5: All same color (all 2s)
Input: [2,2,2]
Output: [2,2,2]
Case 6: Two colors only (0s and 2s)
Input: [2,0,2,0]
Output: [0,0,2,2]
Case 7: Single element
Input: [1]
Output: [1]
Case 8: Two elements
Input: [2,0]
Output: [0,2]
Case 9: Many duplicates
Input: [2,2,0,0,1,1,2,0,1]
Output: [0,0,0,1,1,1,2,2,2]
Common Mistakes
Mistake 1: Incrementing mid after swapping with high
❌ Wrong:
swap(nums, mid, high);
high--;
mid++; // BUG! Need to check swapped element
✓ Right:
swap(nums, mid, high);
high--;
// Don't increment mid
Mistake 2: Wrong loop condition
❌ Wrong: while (mid < high)
✓ Right: while (mid <= high)
Reason: Need to process element at high index
Mistake 3: Not swapping when nums[mid]==0
❌ Wrong: Just move pointers without swap
✓ Right: Swap with low, then move both
Mistake 4: Swapping and moving wrong pointers
❌ Wrong:
if (nums[mid] == 0) {
swap(nums, mid, high); // Wrong pointer!
}
✓ Right:
if (nums[mid] == 0) {
swap(nums, low, mid);
}
Mistake 5: Using extra space
❌ Wrong: Create new array
✓ Right: Sort in-place with swaps
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Counting Sort (Two Pass)
Time: O(n) - two passes
Space: O(1)
Use: Simple, reliable
Issue: Not one-pass
Approach 2: Dutch National Flag (One Pass - OPTIMAL)
Time: O(n) - single pass
Space: O(1)
Use: Optimal solution
Benefit: Elegant, efficient, one-pass
🔑 The Core Insight
Problem: Partition array into three groups
Dutch National Flag Algorithm:
→ Three pointers: low, mid, high
→ Three regions: [0s | 1s | 2s]
→ Process unknowns in middle
Key decisions at mid:
- 0 found → move to left (swap with low)
- 1 found → keep in middle (just advance mid)
- 2 found → move to right (swap with high, don't advance mid)
Why don't advance mid when swapping with high?
→ Swapped element from high is unknown
→ Must examine it in next iteration
🎯 Pattern Recognition
Problem Type: Three-Way Partitioning
Core Pattern: Three pointers for region boundaries
When to Apply:
✓ Need to partition into three groups
✓ In-place sorting required
✓ Elements have three distinct values
✓ One-pass requirement
Key Techniques:
→ Low/Mid/High pointers
→ Swap elements between regions
→ Maintain invariants for each region
→ Don't advance mid after swapping with high
Related Problems:
- Partition Array (LC 75)
- Sort List (LC 148)
- Quick Sort variations
- Three-way partitioning problems
🧠 Interview Strategy
Step 1: "Need to sort 0s, 1s, 2s in-place"
Step 2: "Counting sort works - two pass O(n)"
Step 3: "For one-pass: Dutch National Flag algorithm"
Step 4: "Three pointers: low for 0s, mid to scan, high for 2s"
Step 5: "Partition array into [0s | 1s | 2s] regions"
📝 Quick Revision Notes
🎯 Core Concept:
Use three pointers (low, mid, high) to partition array into three regions: [0s | 1s | 2s] in one pass.
⚡ Quick Implementation:
public void sortColors(int[] nums) {
// // Approach 1 - using 3 counters - straight forward
// int count0 = 0, count1 = 0, count2 = 0;
// for(int num : nums) {
// switch (num) {
// case 0:
// count0++;
// break;
// case 1:
// count1++;
// break;
// case 2:
// count2++;
// break;
// default:
// break;
// }
// }
// int i = 0;
// while(count0-- > 0) {
// nums[i++] = 0;
// }
// while(count1-- > 0) {
// nums[i++] = 1;
// }
// while(count2-- > 0) {
// nums[i++] = 2;
// }
// Approach 2 - little efficient with one-pass
int low = 0; // numbers below than this (strictly, i.e. low - 1) index are 0s
int mid = 0; // numbers between [low, high - 1]
int high = nums.length - 1; // numbers equal or above than this (not strictly) index are 2s
while (low <= mid && mid <= high) {
if(nums[mid] == 0) {
// If a 0 is at mid, push it to low as numbers below index low are always 0 and low++ and mid++.
int temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] == 2) {
// If a 2 is at mid, push it to high - 1 as numbers above greater than or equal to index high always 2.
int temp = nums[high];
nums[high] = nums[mid];
nums[mid] = temp;
high--; // we do not know what got transferred to mid, hence, should not move mid.
} else {
mid++; // already 1 is in correct region
}
}
}
🔑 Key Insights:
- Three pointers: low (0s boundary), mid (current), high (2s boundary)
- Three regions: [0s | 1s | 2s]
- When 0: swap with low, advance both low and mid
- When 1: just advance mid (stays in middle)
- When 2: swap with high, advance only high (not mid!)
- Don't advance mid after swapping with high (must check swapped element)
- Loop condition:
mid <= high(notmid < high) - One pass O(n) time, O(1) space
🎪 Memory Aid:
"0 goes left, 2 goes right, 1 stays middle!"
Think: "Dutch flag - three colors, three regions, three pointers"
Related Patterns
- Partition Array (LC 75)
- Sort List (LC 148)
- Wiggle Sort (LC 280)
Happy practicing! 🎯