Difficulty: MediumTwo Pointers

Sort Colors

Problem in Plain English

Given an array nums holding only 0s, 1s and 2s, sort it in place so that all 0s come first, then all 1s, then all 2s. You must solve it without calling the built-in sort function.

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, in the order red, white, then blue.

The integers 0, 1 and 2 stand for red, white and blue. You must solve this problem without using the standard library sort function.

Constraints

n == nums.length
1 <= n <= 300
nums[i] is 0, 1 or 2.

Examples

Example 1

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Reordering in place groups the two 0s first, the two 1s next and the two 2s last.

Example 2

Input: nums = [2,0,1]
Output: [0,1,2]

The three colours each appear once, so the sorted array is [0, 1, 2].

Example 3

Input: nums = [1]
Output: [1]

The single value is already in order. Its position must still be processed when the two unknown-region boundaries meet.

Example 4

Input: nums = [1,2,0]
Output: [0,1,2]

After passing the initial 1, moving 2 to the end brings 0 into the scanning position. Re-examine it and swap it in front of the 1; skipping it would leave [1, 0, 2] unsorted.

Intuition

Treat the values as three labeled buckets: 0 belongs at the front, 2 at the back, and 1 between them. Counting can rebuild those buckets after recording their sizes. A one-pass alternative grows finished buckets at both ends and classifies only the unknown middle. In [2, 0, 2, 1, 1, 0], moving the first 2 to the back brings a 0 into its position; that new value must be examined before the scanning pointer moves. Both methods change the supplied array and return no new array.

Approaches

Counting Sort

Solution Details

Reveal Counting Sort: intuition, complexity, and code

Intuition

Only three values exist, so counting how many of each appear tells you exactly where every block belongs. A first pass tallies the counts and a second pass repaints the array block by block.

Step-by-Step Logic

Initialize the three tallies to zero, then read every value without modifying the array. Increment its matching tally.
For Example 1, [2, 0, 2, 1, 1, 0] ends with count0 = 2, count1 = 2, and count2 = 2.
Make a second pass with index i. If i < count0, write 0; if i < count0 + count1, write 1; otherwise write 2.
Example 1 writes zeros at indices 0, 1, ones at 2, 3, and twos at 4, 5, producing [0, 0, 1, 1, 2, 2].
Finish without returning an array. The caller observes the rewritten original array; this two-pass method does not meet the one-pass follow-up.

Why It Works

During the first pass, each tally equals the occurrences of its value in the prefix read so far. No values are changed until all frequencies are known. In the second pass, the index ranges have lengths count0, count1, and n - count0 - count1 = count2. Filling those ranges with 0, 1, and 2 therefore preserves exactly the original multiplicities and places each value before every larger value. The output is sorted and occupies the same array. This works for encoded values; rewriting colors would not preserve the identities of separate objects carrying extra data.

Dry Run

Counting Sort: variable states at each step
Pass	Index read or written	Value read or written	Counts after (0,1,2)	Array after
Initialize	none	none	`(0,0,0)`	`[2,0,2,1,1,0]`
Count	`0`	read `2`	`(0,0,1)`	`[2,0,2,1,1,0]`
Count	`1`	read `0`	`(1,0,1)`	`[2,0,2,1,1,0]`
Count	`2`	read `2`	`(1,0,2)`	`[2,0,2,1,1,0]`
Count	`3`	read `1`	`(1,1,2)`	`[2,0,2,1,1,0]`
Count	`4`	read `1`	`(1,2,2)`	`[2,0,2,1,1,0]`
Count	`5`	read `0`	`(2,2,2)`	`[2,0,2,1,1,0]`
Write	`0`	`0` since `0 < 2`	`(2,2,2)`	`[0,0,2,1,1,0]`
Write	`1`	`0` since `1 < 2`	`(2,2,2)`	`[0,0,2,1,1,0]`
Write	`2`	`1` since `2 < 4`	`(2,2,2)`	`[0,0,1,1,1,0]`
Write	`3`	`1` since `3 < 4`	`(2,2,2)`	`[0,0,1,1,1,0]`
Write	`4`	`2`, final block	`(2,2,2)`	`[0,0,1,1,2,0]`
Write	`5`	`2`, final block	`(2,2,2)`	`[0,0,1,1,2,2]`
Finish	none	no returned array	`(2,2,2)`	`[0,0,1,1,2,2]`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

There are n reads and n writes, each with constant work, so two passes take O(n) time. Only three counters and loop variables are stored, giving O(1) extra space. The original array is rewritten rather than replaced; no output array is allocated.

Code

Solution.java

1class Solution {2    public void sortColors(int[] nums) {3        int count0 = 0, count1 = 0, count2 = 0;4        for (int num : nums) {5            if (num == 0) count0++;6            else if (num == 1) count1++;7            else count2++;8        }9        for (int i = 0; i < nums.length; i++) {10            if (i < count0) {11                nums[i] = 0;12            } else if (i < count0 + count1) {13                nums[i] = 1;14            } else {15                nums[i] = 2;16            }17        }18    }19}

Hints

Hint 1

With only three possible values, what would a tally of each value let you rebuild directly?

Hint 2

That tally needs two sweeps; how could swaps place each value correctly the first time you see it?

Hint 3

Keep finished 0s at the front and finished 2s at the back, and handle whatever the scanner points at next.

Edge Cases

Singletons [0], [1], and [2] remain unchanged; even mid == high must be processed.
One repeated value such as [2, 2, 2] produces harmless self/equal-value swaps as high decreases.
A missing category such as [2, 0, 2, 0] sorts to [0, 0, 2, 2]; an empty middle block is valid.
Already ordered [0, 0, 1, 2, 2] remains ordered without relying on a special early exit.
Reverse [2, 1, 0] needs the first and last values exchanged, then processes the middle 1 without a swap.
Re-examination trap [1, 2, 0] requires handling the 0 swapped into mid before advancing it.
At the maximum length 300, counts and pointer arithmetic remain small; the algorithm still uses no size-dependent auxiliary array.

Common Mistakes and Interview Tips

Advancing mid after swapping a 2 with high, even though the swapped-in value at mid has never been inspected.
Looping while mid < high instead of mid <= high, which skips the final meeting position.
Calling the library sort, which violates the explicit no-sort-function requirement.
Rebinding nums to a new sorted array instead of changing the caller's array, or returning a replacement array for this void API.
Describing counting sort as a one-pass method: it first counts and then rewrites. Both approaches use constant extra space, but only partitioning answers the follow-up.
Interview tip: state all four regions, including the finished ones between low and mid. That known one region explains why advancing mid after a zero swap is safe.

Key Takeaway

When input falls into a few known buckets, partition pointers can file every value into its final region in a single pass with constant extra space.