75. Sort Colors
You get an array nums whose entries are only ever 0, 1, or 2 — encoding the colors red, white, and blue. Rearrange the array in place so that all the 0s come first, then all the 1s, then all the 2s, and return it.
Calling your language's built-in sort is off-limits: the point is to exploit the fact that there are only three distinct values. Counting them and rewriting the array is a clean two-pass answer; the classic follow-up asks for a single pass using constant extra space (the Dutch national flag partition).
Example 1:
Input: nums = [1, 2, 0, 1, 2, 0, 0]
Output: [0, 0, 0, 1, 1, 2, 2]
Explanation: The three 0s move to the front, the two 1s sit in the middle, and the two 2s finish the array.
Example 2:
Input: nums = [2, 1, 0]
Output: [0, 1, 2]
Explanation: One of each color: reversing this fully descending arrangement sorts it.
Constraints:
- 1 ≤ nums.length ≤ 300
- nums[i] is 0, 1, or 2
- Library sort functions are not allowed.
Hints:
With only three possible values, a full comparison sort is overkill. Count how many 0s, 1s, and 2s there are in one pass, then overwrite the array with that many of each in order — two passes, O(1) extra space.
For one pass, maintain three regions with pointers low, mid, high: everything left of low is 0, everything right of high is 2, and mid scans the unknown middle. On nums[mid] == 0 swap it to low (advance both); on 2 swap it to high (shrink high only — the value swapped in is unexamined!); on 1 just advance mid. Stop when mid passes high.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 0, 1, 2, 0, 0]
Expected output: [0, 0, 0, 1, 1, 2, 2]