Sort an Array Containing Only 0s, 1s, and 2s
Solve this Problemnums that contains only the values 0, 1, and 2, mixed together in no particular order. Rearrange it in place so every 0 comes before every 1, and every 1 comes before every 2.
Try to do it in a single pass, without calling a general-purpose sort — a three-way partition with three pointers gets you there in O(n) time and O(1) extra space.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
nums[i] is 0, 1, or 2
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int[] sortZerosOnesTwos(int[] nums) { |
| 3 | int[] result = nums.clone(); |
| 4 | int low = 0, mid = 0, high = result.length - 1; |
| 5 | while (mid <= high) { |
| 6 | if (result[mid] == 0) { |
| 7 | int tmp = result[low]; result[low] = result[mid]; result[mid] = tmp; |
| 8 | low++; mid++; |
| 9 | } else if (result[mid] == 1) { |
| 10 | mid++; |
| 11 | } else { |
| 12 | int tmp = result[mid]; result[mid] = result[high]; result[high] = tmp; |
| 13 | high--; |
| 14 | } |
| 15 | } |
| 16 | return result; |
| 17 | } |
| 18 | } |
| 19 |
005low and mid both start at 0, high starts at the last index (5). Everything before low will be 0s, everything from low up to mid will be 1s, and everything after high will be 2s — the middle, unexplored region is [mid, high].
Approach & Solutions
Brute Force — Built-in Sort
BruteJust hand the whole array to a general-purpose sorting algorithm and let it do the work. Correct and trivial to write, but it ignores the fact that there are only three possible values here — a comparison sort spends O(n log n) time solving a problem that doesn't actually need any comparisons at all.
O(n log n)O(n)1class Solution {
2 public int[] sortZerosOnesTwos(int[] nums) {
3 int[] result = nums.clone();
4 Arrays.sort(result);
5 return result;
6 }
7}Better — Counting Pass
BetterCount how many 0s, 1s, and 2s appear, then build a fresh array by writing that many 0s, followed by that many 1s, followed by that many 2s. It's linear time, but it makes two full passes over the data and needs a second array the size of the input.
O(n)O(n)1class Solution {
2 public int[] sortZerosOnesTwos(int[] nums) {
3 int zeros = 0, ones = 0, twos = 0;
4 for (int num : nums) {
5 if (num == 0) zeros++;
6 else if (num == 1) ones++;
7 else twos++;
8 }
9 int[] result = new int[nums.length];
10 int idx = 0;
11 for (int i = 0; i < zeros; i++) result[idx++] = 0;
12 for (int i = 0; i < ones; i++) result[idx++] = 1;
13 for (int i = 0; i < twos; i++) result[idx++] = 2;
14 return result;
15 }
16}Optimal — Three-Way Partition (Dutch National Flag)
OptimalWalk the array once with three pointers: low marks where the next 0 belongs, high marks where the next 2 belongs, and mid scans forward. If nums[mid] is 0, swap it to the low region and advance both low and mid. If it's 1, it's already in the right region — just advance mid. If it's 2, swap it out to the high region and shrink high, but don't advance mid yet — the value swapped in from high still needs to be checked. One pass, no extra array.
O(n)O(1) extra1class Solution {
2 public int[] sortZerosOnesTwos(int[] nums) {
3 int[] result = nums.clone();
4 int low = 0, mid = 0, high = result.length - 1;
5 while (mid <= high) {
6 if (result[mid] == 0) {
7 int tmp = result[low]; result[low] = result[mid]; result[mid] = tmp;
8 low++; mid++;
9 } else if (result[mid] == 1) {
10 mid++;
11 } else {
12 int tmp = result[mid]; result[mid] = result[high]; result[high] = tmp;
13 high--;
14 }
15 }
16 return result;
17 }
18}