how to find the count of an element which repeats maximum number of times in an array if the array contains both positive and negative elements in most efficient way ?
in O(n)?
If the range of elements are small that is in the range of <=10^6 we can create a frequency array say FREQ. For each element the count in the frequency array we have to increment. Initially all values in FREQ are zeros. When you start reading input and say you read a number x, you should add 1 to FREQ[x]. It takes O(N) time to build this array after initialization. When all input values have been scanned, one could make iteration at the FREQ array to find the smallest element with the largest count.
By using O(N) you can find the largest element in the frequency array and save the index of the largest number in the FREQ array and that will be the answer 
But this will work only for +ve numbers 
i did not see the last portion. Sorry
HAPPY CODING
I am not sure can you try this with map?
Take a look at this codehere
By using MAP we have get the count with lesser time complexity i mean by O(n)=log n. I guess that will be better than O(n) 
If you can tell the question then we can give a try.
This is the code i submitted to find out the maximum count element in an array. I mean for the MAX_COUNT problem.
4 Likes
Both the methods mentioned in answers before my answer,
-
Using a map.
-
Using an array.
Can be used, depending on the question.
The interesting thing here is that,
the element access time of a map is O(log(n)). Detailed discussion: link1 and link2
the element access time(element look up) of an array is always O(1).
So, when you update the frequency at some index in a map, it takes O(log(n)) but it takes only O(1) in an array.
So, if both methods can be used and the time limit is strict, try to use an array
For example: std::map< int,int > m;
m[i]++; updation will have O(log(n)) complexity
but in case of an array int m[1000];
m[i]++; will have O(1) complexity
Well I have an idea. If the numbers can be negative or large (eg: 10^9), then arrays cannot be used. Then we are using map and time complexity will be nlogn. But this will also have lot of dynamic memory allocation factors, etc that slow down the code.
So, a simpler way is to sort the array in O(nlogn) and then traverse it to find the most repeating element.
range of elements -10^9 to 10^9
how to build frequency array for negative elements?
I have posted another method.
Can you please tell whether it is working or not? Or tell the question?
this is the best method
2 Likes
@kuruma: thanks dude. It is a bit disappointing that even after debugging the whole wrong code submitted here and theses ppl they dont even turn back after getting the benifit Not even just a thanks or an up-vote. I dont know whether he is satisfied with this method :
Anyway thanks @kuruma 
glad to find you here again
1 Like
how is this the best method?
the element access time of a map is O(log(n)).
the element access time(element look up) of an array is always O(1).
So, when you update the frequency at some index in a map, it takes O(log(n)) but it takes only O(1) in an array.
So, if both methods can be used and the time limit is strict, shouldn’t we try to use an array
For example: std::map< int,int > m;
m[i]++; updation will have O(log(n)) complexity
but in case of an array int m[1000];
m[i]++; will have O(1) complexity
This is something to consider when we solve the problem.
Read the question properly @pratku123. the range is between **-**10^9 to 10^9. How can you store the frequency of negative numbers in array index?
@suryanit: If you have understood the answer can you please accept the answer so that we can close this question .