Example 1
ready- Input
nums = [ 2, 0, 2, 1, 1, 0 ]- Expected
[ 0, 0, 1, 1, 2, 2 ]- Why
- equal colors group together in 0, 1, 2 order
Sort Colors
35 min · sortColors()mediumOpen in LeetCode #75 ↗
Three paint colors have spilled into one row of cans. Each can is labeled 0, 1,
or 2, and you need the labels grouped in that order.
Given an integer array nums containing only 0, 1, and 2, return the
array sorted with every 0 first, then every 1, then every 2.
Think of 0 as red, 1 as white, and 2 as blue. The names add a story;
the numeric order decides the result.
A few ground rules:
- Keep every value exactly once; only its position may change.
- Return an array with the same length as the input.
- The intended solution groups all three colors in one scan with constant extra space.
Constraints
1 <= nums.length <= 100_000nums[i] ∈ {0, 1, 2}
Hints
Count before you rearrange
Since there are only three possible values, you can count each one and overwrite the array with the right number of zeroes, ones, and twos.
Split the row into four regions
Track a finished 0 region on the left, an unknown region in the middle, and a
finished 2 region on the right. Values between the left boundary and your
scanner are the finished 1 region.
A swapped-in value is still unknown
When the scanner finds 2, swap it with the right boundary and shrink that
boundary. Don't advance the scanner yet: the value arriving from the right hasn't
been classified.
Follow-up
Can you finish in one pass without calling a general-purpose sorting routine?
Visible cases
Examples
Example 2
ready- Input
nums = [ 2, 2, 2 ]- Expected
[ 2, 2, 2 ]- Why
- a single-color row is already grouped
Example 3
ready- Input
nums = [ 2, 0, 1 ]- Expected
[ 0, 1, 2 ]- Why
- one of each color lands in numeric order
Interview signal
Asked at
MicrosoftAmazonMeta
Count then rebuild
Only three values can appear, so a general-purpose sort is unnecessary. Count each color, then overwrite the array in color order.
def sort_colors(nums: list[int]) -> list[int]:
counts = [0, 0, 0]
for color in nums:
counts[color] += 1
write = 0
for color, count in enumerate(counts):
for _ in range(count):
nums[write] = color
write += 1
return numsThis is already fast and uses no second n-sized array. Its one weakness is structural: it needs one pass to count and another to rebuild.
Time O(n) — two linear passes. Space O(1) — exactly three counters.
Dutch flag partition
The Dutch national flag partition is a one-pass method that keeps three value groups and one not-yet-classified region. Use three indices:
low: the next position for a0.mid: the value you're classifying now.high: the next position for a2.
Before each step, positions before low are zeroes, positions from low to
mid - 1 are ones, and positions after high are twos. Everything from
mid through high is still unknown.
def sort_colors(nums: list[int]) -> list[int]:
low = 0
mid = 0
high = 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 -= 1
return numsThe 2 case is the trap. You shrink high but leave mid in place because the
value swapped in from the unknown region still needs inspection. In the 0 case, advancing
both pointers is safe: anything swapped from low came from the finished one-region.
Time O(n) — each step shrinks the unknown region. Space O(1) — only three indices.
LeetCode's version mutates the array in place and returns void; ours returns the resulting array so the judge can compare it.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 0, 0, 1, 1, 2, 2 ]
Run: visible + custom · Submit: full suite