Back to Two Pointers
Medium
Sort Colors
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, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.
Examples
Input:nums = [2,0,2,1,1,0]
Output:[0,0,1,1,2,2]
Input:nums = [2,0,1]
Output:[0,1,2]
Constraints
n == nums.length1 <= n <= 300nums[i] is either 0, 1, or 2.
Approach
Since there are only 3 possible values (0, 1, and 2), we can iterate through the array once to count the number of 0s, 1s, and 2s. Then, in a second pass, overwrite the array with the correct number of 0s, followed by 1s, followed by 2s.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
This requires two passes over the array. The problem often asks if it can be done in a single pass.
Solution.java
class Solution { public void sortColors(int[] nums) { int count0 = 0, count1 = 0, count2 = 0; // First pass: count frequencies for (int num : nums) { if (num == 0) count0++; else if (num == 1) count1++; else count2++; } // Second pass: overwrite array for (int i = 0; i < nums.length; i++) { if (i < count0) { nums[i] = 0; } else if (i < count0 + count1) { nums[i] = 1; } else { nums[i] = 2; } } }}