Leetcode 75. Sort Colors

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){
                case 0:
                    countZero++;
                    break;
                case 1:
                    countOne++;
            }
        }
        int currentIndex = -1;
        while(0<countZero--){
            nums[++currentIndex] = 0;
            // countZero--;
        }
        while(0<countOne--){
            nums[++currentIndex] = 1;
            // countOne--;
        }
        while(currentIndex<nums.length-1){
            nums[++currentIndex] = 2;
        }
    }
}

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007