Sort Colors
(#75), Medium
Category: Array, Two Pointer, Sorting
Problem Statement
You’re given an array nums with n objects colored red, white, or blue. Your task is to sort them in-place so that objects of the same color are adjacent, and in the order: Red (0), White (1), Blue (2). 📌 You must solve it without using any built-in sort function.
Examples
Input: [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: The array is sorted in-place into grouped colors in the order 0, 1, 2.
Input: [2, 0, 1]
Output: [0, 1, 2]
Explanation: Each color is positioned correctly without using built-in sort.
Approach
Counting Sort
- Initialize three counters: `zero`, `one`, and `two` to 0.
- Iterate through the array once to count the occurrences of 0, 1, and 2.
- Overwrite the original array using the counts in order: fill with 0s, then 1s, then 2s.
var sortColors = function(nums) {
let zero = 0, one = 0, two = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) zero++;
else if (nums[i] === 1) one++;
else two++;
}
let i = 0;
while (zero--) nums[i++] = 0;
while (one--) nums[i++] = 1;
while (two--) nums[i++] = 2;
return nums;
};Complexity
Time: O(n) – Each element is visited once during counting and once during writing.
Space: O(1) – No extra space used except fixed counters.