Sort an array of 0s, 1s and 2s gfg solution
Problem Statement
Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.
Example 1:
Input:
N = 5
arr[]= {0 2 1 2 0}
Output:
0 0 1 2 2
Explanation:
0s 1s and 2s are segregated
into ascending order.Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Approach
Here we have to sort the array of 0s,1s, and 2s we can use another approach like sorting algorithms,
but the time complexity will be more for sorting algo so we cannot use here the sorting algorithm
We'll use a counting-based approach to solve this problem efficiently. Here's how we'll implement it:
- We'll iterate through the array once, counting the occurrences of 0s, 1s, and 2s.
- After counting, we'll re-arrange the array by placing the counted number of 0s, 1s, and 2s in ascending order.
- We'll use three variables count0, count1, and count2 to count the occurrences of 0s, 1s, and 2s, respectively.
- Then, we'll iterate through the array again, filling in the elements according to their counts.
Solution :
class Solution {
sort012(arr, N)
{
//your code here
let count0=0; /// taking the count0 variable to count the zeroes
let count1=0; /// taking the count0 variable to count the ones
let count2=0; //taking the count0 variable to count the 2
for(let i=0; i<=arr.length-1; i++){ /// running the loop from 0 to arr.length
if(arr[i]==0){
count0++ // here whenever the arr[i] is equal to zero count0 will increment
}else if(arr[i]==1){
count1++;//here whenever the arr[i] is equal to zero count1 will increment
}
else if(arr[i]==2){
count2++ //here whenever the arr[i] is equal to zero count2 will increment
}
}
After counting the zeros one and two now we have to re-arrange the array taking the index=0; so that we will re-arrange it
let index=0;
while(count0>0){ // running the loop on count0
arr[index]=0 // initially my index=0; now assigning the value to the arr of index
index++; // now increment the index
count0-- /// decrement the count0 because the zero is added
} /// This loop will run till count ==1
while(count1>0){
arr[index]=1
index++;
count1--
}
while(count2>0){
arr[index]=2
index++;
count2--
}
return arr
}
}
Solution
class Solution {
sort012(arr, N)
{ //your code here
let count0=0;
let count1=0;
let count2=0;
for(let i=0; i<=arr.length-1; i++){
if(arr[i]==0){
count0++
}else if(arr[i]==1){
count1++;
}
else if(arr[i]==2){
count2++
}
}
let index=0;
while(count0>0){
arr[index]=0
index++;
count0--
}
while(count1>0){
arr[index]=1
index++;
count1--
}
while(count2>0){
arr[index]=2
index++;
count2--
}
return arr
}
}
Conclusion
By using a counting-based approach, we efficiently sort an array of 0s, 1s, and 2s in ascending order. This approach ensures simplicity and optimal performance, meeting the problem's constraints effectively.
For more insights into algorithms and efficient coding techniques, visit our detailed tutorials and guides!