Sort an array of 0s, 1s and 2s (DSA)

 

Problem statement:(👈click here for GFG)

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.

Example 2:

Input: 
N = 3
arr[] = {0 1 0}
Output:
0 0 1
Explanation:
0s 1s and 2s are segregated 
into ascending order.

Your Task:
You don't need to read input or print anything. Your task is to complete the function sort012() that takes an array arr and N as input parameters and sorts the array in-place.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 10^6
0 <= A[i] <= 2

Solution:

Approach: 

• Initialize three variables, count_0, count_1, and count_2 to 0. These variables will be used to count the number of occurrences of 0s, 1s, and 2s in the given array.

• Traverse the array from left to right and for each element, increment the corresponding count variable based on its value. This will count the number of occurrences of 0s, 1s, and 2s in the array.

• Initialize a new variable i to 0. This variable will be used as an index to update the array.

• Using a while loop, fill the first count_0 elements of the array with 0.

• Using another while loop, fill the next count_1 elements of the array with 1.

• Using a final while loop, fill the remaining count_2 elements of the array with 2.

• Return the updated array.

The main idea behind this approach is to count the number of occurrences of each element in the array, and then update the array with those elements in the correct order. Since this approach traverses the array only once, the time complexity is O(N), where N is the size of the input array. Additionally, the space complexity is O(1), as we are only using a constant amount of extra space to keep track of the counts of each element.

function sort012(arr, N){

let count_0 = 0, count_1 = 0, count_2 = 0;

for(let i = 0; i < N; i++){

if(arr[i] === 0){

count_0++;

}

else if(arr[i] === 1){

count_1++;

}

else{

count_2++;

}

}

let i = 0;

while(count_0 > 0){

arr[i++] = 0;

count_0--;

}

while(count_1 > 0){

arr[i++] = 1;

count_1--;

}

while(count_2 > 0){

arr[i++] = 2

count_2--;

}

return arr;

}

// example usage

let arr = [1, 0, 2, 1, 0];

let sortedArr = sort012(arr, arr.length);

console.log(sortedArr); // [0, 0, 1, 1, 2]

Thank you,

Learning is a never-ending process, and every day is an opportunity to learn something new. Keep exploring, keep pushing your limits, and keep striving towards your goals. Remember that every small step counts, and even the smallest progress is worth celebrating. Don't be afraid to ask questions, seek guidance, and learn from others. With dedication and hard work, you can achieve anything you set your mind to. So keep learning, keep growing, and keep shining!