Sorting Colors Solution in C++
Asked 5 months ago
0Comments
2 Views
Sort Colors - medium level Problem in LeetCode !
if we use sort function ! it s a piece of Cake ! Simple
sort(arr.begin() , arr.end()) According to Leetcode ! we should not use Inbuild Sort Function
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Approch 2 : counting Method !
[2,0,2,1,1,0]
count
0s 2
1s 2
2s 2
and Spread 0 0 1 1 2 2
void sortColors(vector<int>& nums) {
int ones , zeros , twos ;
zeros = ones = twos = 0 ;
for(int i = 0 ; i <nums.size() ; i++){
if(nums[i] == 0){
zeros++ ;
}
else if(nums[i] == 1 ){
ones++ ;
}else{
twos++ ;
}
}
int i = 0 ;
while(zeros--){
nums[i] = 0 ;
i++ ;
}
while(ones--){
nums[i] = 1 ;
i++ ;
}
while(twos--){
nums[i] = 2 ;
i++ ;
}
}The for loop iterates over the nums array once to count the occurrences of 0s, 1s, and 2s.
This loop runs in
O(n) time, where
n is the number of elements in the nums array.
Overwriting the nums array:
The while loops iterate over the nums array to overwrite it with the counted numbers.
These loops together also run in
O(n) time because each loop iterates over the total count of 0s, 1s, and 2s, which together sum up to
Thus, the total time complexity is:
O(n)+O(n)=O(n)
so !
Time Complexity:O(n)
Space Complexity: O(1)
! Well Its not an Optimal Approch !
Third Approch is 3 Pointer Approch
lets consider low medium and High positions !
[2,0,2,1,1,0]
Initially low and medium are at same Position - at 1st index ! and high at last index !
[2,0,2,1,1,0]
(l,m) (h)
and Swap as long as high crosses the medium position !
void sortColors(vector<int>& nums) {
int low = 0, medium = 0, high = nums.size() - 1;
while(medium <= high) {
if(nums[medium] == 0) {
swap(nums[low], nums[medium]);
low++;
medium++;
} else if(nums[medium] == 1) {
medium++;
} else {
swap(nums[medium], nums[high]);
high--;
}
}
}Share