75. Sort Colors (LEETCODE): Approaches with an explanation

Photo by Florian Olivo on Unsplash

Sort Colors - LeetCode

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.

APPROACH 1:

Counting Sort Algorithm

Step 1: Traverse an array and store the total count of 0, 1, and 2 in count variables.

Step 2: Now, replace the array with 0, 1, and 2 according to the count of the numbers.

#include <bits/stdc++.h>
using namespace std;

int main()
{
 int arr[]={1,1,0,0,0,2,2,2,2,1,1,1,0,0};

 int n = sizeof(arr)/sizeof(arr[0]);

 int count0=0, count1=0, count2=0;
// Storing the count
 for(int i=0; i<n; i++){

    if(arr[i]==0){
        count0++;
    }
    if(arr[i]==1){
        count1++;
    }
    if(arr[i]==2){
        count2++;
    }
 }

//Replacing the array.
 for(int i=0; i<count0; i++){
        arr[i]=0;
 }
 for(int i=count0; i<count0+count1; i++){
        arr[i]=1;
 }
 for(int i=count0+count1; i<n; i++){
        arr[i]=2;
 }


//printing the array
 for(int i=0; i<n; i++){
        printf("%d ",arr[i]);
 }



 return 0;
}

Time Complexity: O(3N)

Space Complexity: O(1)

Approach 2:

Dutch National Flag Algorithm or 3 pointers approach

Step 1: Take 3 pointers namely low, mid, high.

Step 2: Traverse the array and arrange the array such a way that 0’s are left to the left pointer and 2’s are on the right of high pointer.

#include <bits/stdc++.h>
using namespace std;

int main()
{
        int arr[]={1,1,0,0,0,2,2,2,2,1,1,1,0,0};

        int n = sizeof(arr)/sizeof(arr[0]);
        int low = 0, mid = 0, high = n - 1;
        
        while (mid <= high) {
            if (arr[mid] == 0) {
                swap(arr[low], arr[mid]);
                low++;
                mid++;
            }
            else if (arr[mid] == 1) {
                mid++;
            }
            else if (arr[mid] == 2) {
                swap(arr[high], arr[mid]);
                high--;
            }
        }

        //printing the array
       for(int i=0; i<n; i++){
          printf("%d ",arr[i]);
       }

 return 0;
}

Time Complexity: O(N)

Space Complexity: O(1)

Hope you find this helpful. Thank you!

Happy to Connect