Sort Colors
Asked at Amazon, Oracle, Walmart
Problem
Given an array nums with n objects colored red, white, or blue (represented as 0, 1, 2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. You must solve it without using the library sort function.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Dutch National Flag algorithm: use three pointers — low (boundary for 0s), mid (current element), high (boundary for 2s). One pass through the array.
The invariants: everything before low is 0, everything after high is 2, everything between low and mid-1 is 1, everything between mid and high is unexamined.
At each step, examine nums[mid]:
- If 0: swap with
nums[low], advance both low and mid. - If 1: just advance mid.
- If 2: swap with
nums[high], decrement high (don't advance mid — the swapped element is unexamined).
Visual walkthrough for [2,0,2,1,1,0]:
low=0, mid=0, high=5.
nums[mid]=2: swap(2,0). [0,0,2,1,1,2]. high=4. mid=0.
nums[mid]=0: swap(0,0). [0,0,2,1,1,2]. low=1, mid=1.
nums[mid]=0: swap(0,0). [0,0,2,1,1,2]. low=2, mid=2.
nums[mid]=2: swap(2,1). [0,0,1,1,2,2]. high=3. mid=2.
nums[mid]=1: mid=3.
nums[mid]=1: mid=4. mid > high, stop.
Result: [0,0,1,1,2,2].
Edge cases: all same color (no swaps needed), empty array, two elements.
Optimal Approach
Step 1: Initialize low = 0, mid = 0, high = n - 1.
Step 2: While mid <= high:
- If nums[mid] == 0: swap nums[low] and nums[mid]. low++, mid++.
- If nums[mid] == 1: mid++.
- If nums[mid] == 2: swap nums[mid] and nums[high]. high--.
Step 3: The array is sorted in-place.
The key insight: when you swap with high, the swapped element is unexamined, so don't advance mid. When you swap with low, the swapped element (a 1) is already in the right zone, so you can advance.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Advancing mid after swapping with high. When you swap nums[mid] with nums[high], the element from high is unexamined, so you must NOT advance mid. Only decrement high.
Swapping low and mid when nums[mid] == 1. A value of 1 is already in the correct partition (between low and mid). You only advance mid, never swap with low for 1s.
Confusing the Dutch National Flag algorithm with simple counting sort. The constraint is to do it in one pass with O(1) space, not two passes with a count array.
Forgetting that everything before low is 0, everything after high is 2, and everything between low and mid - 1 is 1. If you lose track of these invariants, the partition breaks.
Using four pointers or a hash map instead of the three-pointer low/mid/high approach. The problem explicitly forbids library sort, and a hash map uses extra space.
Solution Code
def sortColors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1Frequently Asked Questions
What is the Sort Colors problem?
Given an array nums with n objects colored red, white, or blue (represented as 0, 1, 2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. You must solve it without using the library sort function.
How do you solve Sort Colors?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sort Colors?
Sort Colors is asked at Amazon, Oracle, Walmart. It is a medium difficulty problem.
What are common mistakes on Sort Colors?
- Advancing `mid` after swapping with `high`. When you swap `nums[mid]` with `nums[high]`, the element from `high` is unexamined, so you must NOT advance `mid`. Only decrement `high`.
- Swapping `low` and `mid` when `nums[mid] == 1`. A value of 1 is already in the correct partition (between `low` and `mid`). You only advance `mid`, never swap with `low` for 1s.
- Confusing the Dutch National Flag algorithm with simple counting sort. The constraint is to do it in one pass with `O(1)` space, not two passes with a count array.
- Forgetting that everything before `low` is 0, everything after `high` is 2, and everything between `low` and `mid - 1` is 1. If you lose track of these invariants, the partition breaks.
- Using four pointers or a `hash map` instead of the three-pointer `low`/`mid`/`high` approach. The problem explicitly forbids library sort, and a `hash map` uses extra space.