Optimizing Sorting Algorithm For Three Colors In O(N) Time Complexity

Intuition

The basic intuition comes from sorting.

  
  
  Approach

In the naive approach, we can sort the array using inbuilt sorting function. The time complexity will be O(N*log(N)).

Optimize: 
Since we are sorting only three numbers, we can use the concept of counting sort. Keep track of number of zeros and number of ones in the array.

  
  
  Complexity


Time complexity: O(N)

Space complexity: O(1) 


  
  
  Code


class Solution {
    public void sortColors(int[] nums) {
        int countZero = 0;
        int countOne  =  0;
        for(int num: nums){
            switch(num){...