Problem - Sorting in linear time

#1

I have seen the hint video for this problem but am not able to understand the logic behind the solution.

#2

The array contains only elements 0,1 and 2. To sort this array in linear time, you can also do one more thing -
Initialise 3 variables a, b, c as 0. These variables will keep the count of your numbers 0, 1 and 2.
a stores the number of times 0 appears in the array.
b stores the number of times 1 appears in the array.
c stores the number of times 2 appears in the array.
This can be done in linear time.
Finally again traverse the array from starting and store the elements suitably.
Tell me if you are able to code this approach. Otherwise I will help you.

#3

Using your suggested approach, I coded this https://ide.codingblocks.com/s/208756.
It works fine for all the cases. Is this code fine or it can be optimized further?

#4

Well if it works for you then its fine. And it cannot be done in less than O(n) time complexity.

#5

Okay, thanks for your help.

#6

@lalchetna03 Please mark your doubt as resolved now.