Given an array of three group of elements sort them in order
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
One Simple way is to use Counting Sort algorithm
Algorithm:
- initialize a bucket(array)
- Loop through each element and increment the bucket[i]
- Loop through the bucket and update existing nums
Code:
var sortColors = function(nums) {
let bucket = new Array(3).fill(0);
for (let i = 0; i < nums.length; i++) {
bucket[nums[i]]++;
}
let bucketIdx = 0;
for (let i = 0; i < nums.length; i++) {
console.log(bucketIdx);
if (bucket[bucketIdx] != 0) {
nums[i] = bucketIdx;
bucket[bucketIdx]--;
} else {
bucketIdx++;
i--
}
}
return nums
};
This can also be solved in one pass:
Algorithm:
- initialize low and mid to 0 and high to nums last index
- Now, consider mid as center pole
- Whenever you encounter nums[mid] as 0, swap nums[mid] and nums[low] then increment low and mid. We increment low, so that next 0 will take that index and same with mid
- Whenever nums[mid] is 1, just increment mid
- Whenever nums[mid] is 2, swap nums[mid] and nums[high] and decrement high. This way we are putting all 2’s at the end
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
let temp = nums[mid];
nums[mid] = nums[low];
nums[low] = temp;
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
let temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
}
}
};