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