COUNT OF MAXIMUM REPEATING ELEMENT IN THE ARRAY

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 :slight_smile:

But this will work only for +ve numbers :frowning: 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) :slight_smile:

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,

  1. Using a map.
  2. 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*++; updation will have O(log(n)) complexity
    but in case of an array int m[1000];


    m*++; 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 :frowning: Not even just a thanks or an up-vote. I dont know whether he is satisfied with this method :
Anyway thanks @kuruma :smiley: glad to find you here again :slight_smile:

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*++; updation will have O(log(n)) complexity

but in case of an array int m[1000];

m*++; 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?

@bipin2
Thanks for the clarification.
In that case, this method is the best.
Good Answer!

@pratku123: thanks bro!! Suggestions are always welcome :slight_smile:

@suryanit: If you have understood the answer can you please accept the answer so that we can close this question . :slight_smile: