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