Sort Colors - LeetCode

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:

1. initialize a bucket(array)
2. Loop through each element and increment the bucket[i]
3. 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:

1. initialize low and mid to 0 and high to nums last index
2. Now, consider mid as center pole
3. 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
4. Whenever nums[mid] is 1, just increment mid
5. 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--;
    }
  }
};

Comments

[Ravi Mishra]

I implemented these two methods exactly. First one has an extra space of O(n) and the other one is constant space O(1). Runtime of both functions is O(n). This problem is also called Dutch National Flag problem.