Q5) Arrays — Sort Colors

Question Link — https://leetcode.com/problems/sort-colors/description/

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.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Approach 1 — Counting Sort Algo

This algo is used when we know that the array has a short range of values like here we have 0’s 1’s and 2’s only. So we maintain a count of 0’s 1’s and 2’s

TC — O(n) , SC — O(1)

In one pass count the number of 0’s 1’s and 2’s. And in the other pass run while loops that exhaust at the count and return the array.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count0 = 0;
        int count1 = 0;
        int count2 = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i] == 0) count0++;
            else if(nums[i] == 1) count1++;
            else count2++;
        }
        int i = 0;
        while(count0 > 0)
        {
            nums[i] = 0;
            i++;
            count0--;
        }
        while(count1 > 0)
        {
            nums[i] = 1;
            i++;
            count1--;
        }
        while(count2 > 0)
        {
            nums[i] = 2;
            i++;
            count2--;
        }
    }

};

Approach 2 — Dutch National Flag Algorithm.

This algo is a one pass algorithm that can be used for sorting the values or as the name goes … it can be used for sorting the colors of the Dutch National Flag.

Maintain three pointers, low mid and high. At the start point low and mid at 0th index of the array and high at the last index of the array (n-1)

Now the algo basically states that the mid pointer is the one that indicates our current number that we are dealing with here and if we encounter a high value (in this case 2) by the mid pointer then we swap (nums[mid],nums[high]) which makes it so that every high value is at the very rightmost end of the array. After swapping we need to decrement the high pointer.

Now if we encounter a mid value (in this case 1) then we just move the mid pointer forward by one place. mid++;

And if we encounter a low value then we swap(nums[low],nums[mid]) and increment both the pointers together.

TC — O(n) [its one pass tho], SC — O(1)

Code:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = nums.size()-1;
        while(mid <= high)
        {
            if(nums[mid] == 2)
            {
                swap(nums[mid], nums[high]);
                high--;
            }
            else if(nums[mid] == 1)
            {
                mid++;
            }
            else if(nums[mid] == 0)
            {
                swap(nums[low],nums[mid]);
                low++;
                mid++;
            }
        }
    }
};

Refer this video for more clarity —