How to do in linear timee?

#1

Do i have to count each no and then put them one by one in the array to have a linear time??
That doesn’t look like a good approach

#2

Hi @bhavik911,
Yes that is exactly what needs to be done. You can either take 3 variable to count the number of occurrences or use a array. When the limits are small then we use array or hashmap to store the count as it reduces the time complexity.

#3

So I just store all the nos and then print them , is that it?? Is this all efficient , can you please guide me on this

#4

How do i store the elements in the array directly ??

#5

Like without knowing how many the count of digits how can i store them in a same array in sorted manner

#6

Should I use arraylist here?? Can you please review my code?

#7

You use index as number for example if the numbers are 0,0,1,1,1 then you can simple make a array arr and then store arr[0]=2 and arr[1]=3 … Note that you cannot store negative number as index can never be negative .

#8

No your code is highly inefficient. You do not need 3 arraylist that is worse than making 3 variable … Use the method i told in the above message. Just store number as index of array and count as value at that index … I have given a example in above message hope that would help you.This method is more discussed in hashmap.

#9

But doent’t this require 3 for loops to print the element??

#10

Well it can be done easily in two loops but even if you take 3 loops then will run in total of n times which is the total sum of number of 0,1,2. From inefficient i meant space inefficient. Your code creates 3 arraylist and you insert 0 and ones again and again in that which is not necessary. You can simple create a array of size 3 to keep count of number of occurrence. As we know arr[0] will always be incremented when a zero occurs hence we can keep a count of number of times 0 came and then print that much zero in the beginning followed by ones and twos.