#75 Sort Colors
frequently reported atWalmartMicrosoftTCSAmazonByteDance / TikTokBloomberg
the problem
In plain words
nums contains only 0, 1 and 2 (red, white, blue). Sort it in place so equal colours are adjacent, in order 0, 1, 2 — without the library sort.
in nums = [2,0,2,1,1,0]
out [0,0,1,1,2,2]
in nums = [2,0,1]
out [0,1,2]
- 1 ≤ n ≤ 300
- nums[i] ∈ {0,1,2}
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternThree-way partition (Dutch flag)Counting / bucket sort
Keep three zones — 0s at the front, 2s at the back, 1s in the middle — and shrink the unknown zone one element at a time. It's the 3-way partition at the heart of 3-way quicksort.
solutions
From brute force to optimal
Call Arrays.sort — fine in real life, forbidden here.
- Arrays.sort(nums).
A general comparison sort ignores that there are only 3 values.
The dual-pivot quicksort's recursion stack.
class Solution { public void sortColors(int[] nums) { Arrays.sort(nums); // works, but the problem forbids it and it's O(n log n) }}Count 0s, 1s, 2s, then write them back in order (counting sort).
- Count each colour.
- Overwrite nums.
Two passes.
Three counters.
class Solution { public void sortColors(int[] nums) { int[] count = new int[3]; for (int x : nums) count[x]++; int i = 0; for (int color = 0; color < 3; color++) while (count[color]-- > 0) nums[i++] = color; }}low/mid/high pointers; 0 → swap to low, 1 → skip, 2 → swap to high.
- low = mid = 0, high = n−1.
- While mid ≤ high, act on nums[mid].
- After swapping with high, do not advance mid.
Every step shrinks the unknown zone by one.
Three indices.
class Solution { public void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { swap(nums, low++, mid++); // 0 goes to the front } else if (nums[mid] == 1) { mid++; // 1 is already in the middle } else { swap(nums, mid, high--); // 2 goes to the back; re-check nums[mid] } } } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }}Dry run
in the room
How to say it in the interview
talk track
- Counting sort is a perfectly good first answer; the follow-up "one pass?" is the cue for Dutch flag.
- Explain the invariant of the four zones (0s | 1s | unknown | 2s); it proves correctness.
traps
- Advancing mid after swapping with high — the value that arrived is still unchecked.
what they ask next
Follow-ups
k colours instead of 3?
Counting sort in O(n + k), or recursive 3-way partitions ("rainbow sort") in O(n log k) with O(1) space.
before you submit
Edge cases to test
- One element: nothing to do.
- Only one colour, e.g. [1, 1] or [2, 2].
- Already sorted, or fully reversed [2, 2, 1, 1, 0, 0].
- A 2 swapped in from the back must be checked again — [2, 0, 2] catches a wrong mid++ after that swap.
practise next
Similar problems
- #283Move ZeroesEasyin Two Pointers
- #912Sort an ArrayMediumin Sorting
- #324Wiggle Sort IIMediumin Sorting