Leetcode 75. Sort Colors

Published at

1/11/2025

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

dev-resources.site

Leetcode 75. Sort Colors

Intuition

Approach

Complexity

Code