Find maximum occuring integer (Mode) in an unsorted array

Question

How to find the integer occurring maximum number of times (mode) in an unsorted array of integers?

One O(nlogn) approach I could think of is to sort. Is there any other better approach?

Answer 1

If you are using Linq you can do this

IEnumerable.Max();

Answer 2

I think you want to find out element that has most occurences in the array - if you don't care about memory, traverse the array once, increase count of each element in the hashtable. Then find the one with highest count. You'd need one traverse of array and one of the hashtable.

so in pseudocode:

hashtable hash;
foreach(element in array){
  if(!hash.contains(element))
    hash[element] = 1;
  else 
    hash[element]++;
}

int max = 0;
max_element;
foreach(element in hash)
   if(hash[element] > max)
   {
     max_element = element;
     max = hash[element];
   }

//max_element contains the maximum occuring one.

Answer 3

You can use a hashtable with "the number in array" as key and "occurrences" as values.

Sample code be like this:

 hashtable h;
 for every entry in array
      search hashtable
           if present, increment num_occurrences
           else, create new entry

 Iterate over all the entries in hashtable and return one 
 with max num_occurrences

As searching in hash is considered O(1), the overall complexity will be O(n).

A special case of this problem is when the numbers in array are in a given range, in that case take another array of ints with size of maximum value in the original array,and use the index of new array as key and the number stored in this array as count of occurrences.

Return the index of the largest value in this array.