DAY 4 - Dutch National Flag Algorithm

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-4.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

DAY-4 PROBLEM 1
Given an array A[] consisting of only 0s, 1s, and 2s. The task is to write a function that sorts the given array. The functions should put all 0s first, then all 1s and all 2s in last.

This problem is also the same as the famous “Dutch National Flag problem”. The problem was proposed by Edsger Dijkstra. The problem is as follows:

Example:
Input: {0, 1, 2, 0, 1, 2}
Output: {0, 0, 1, 1, 2, 2}

"Given N balls of colour red, white or blue arranged in a line in random order. You have to arrange all the balls such that the balls with the same colours are adjacent with the order of the balls, with the order of the colours being red, white and blue (i.e., all red coloured balls come first then the white coloured balls and then the blue coloured balls)".

Intuition:

The problem looks pretty easy at first and trust me it is but probably not the way a beginner would look at it.
We can go for the most obvious approach or say a brute force approach in this case. It is to sort the array and we will simply get the desired result.

Approach

Brute Force Approach:

• Sort the array using inbuilt library function or create a function that sorts it.

Code:

void sortColors(vector<int>& nums) {
        sort(nums.begin(),nums.end());
    }

Complexity Analysis

Time Complexity: O(nlogn)
Space Complexity: O(1)

Optimal Approach
We are going to take an approach that allows us to solve the problem in one pass. Henceforth making the time complexity O(n) while only using constant space.
Our Approach will be Dutch National Flag Algorithm (An Odd name I know).

• The Dutch National Flag algorithm, also known as 3-way partitioning, is an algorithm for sorting an array containing three distinct values. The algorithm was designed to solve the problem of sorting an array containing only 0s, 1s, and 2s, which is similar to the problem in the given question.

• The algorithm works by maintaining three pointers: low, mid, and high. The low pointer points to the beginning of the array, the high pointer points to the end of the array, and the mid pointer starts at the beginning of the array and moves through it.

• The goal is simple. We want to keep all the 0's on the left of low pointer, all the 2's on the right side of high pointer and all the 1's in between both these pointers.

• As we traverse through the array, If we find a 0 we will swap it with the low pointer and increase the low pointer by 1. The value uses mid pointer as the iterator through whole array. If we find a 1 we keep it as it is and increase the mid pointer. If we find a 2 we swap it with the high pointer and decrease high pointer by 1.

• At the end of it we terminate the loop if our mid pointer crosses our high pointer.

Code:

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

            }
            else if(nums[mid] == 2)
            {
                swap(nums[mid],nums[high]);
                high--;
            }
            else
            {
                mid++;
            }
        }

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)