Sort Colors(#75)
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
Count the number of 0s, 1s, and 2s in the array. Then, overwrite the original array with those many 0s, 1s, and 2s in order.
💻 Code
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;
};
console.log(sortColors([2, 0, 2, 1, 1, 0])); // [0, 0, 1, 1, 2, 2]📈 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.