Find the number in an array which occurred most number of times

Question

Given an integer array, i need to find which number occurred most number of times. I have written algorithm as below.

1. Use a map to store number and number of times it occurred.

   map<int, int>

   Key: represents the number
   value: represents number of times key occurred.

2. Scan input array and update the map with number and number of occurances.
3. Iterate through map from the begining to end. Find the key for which maximum value is present. This key becomes the number which occurred most number of times.

I implemented the algorithm as below.

#include <iostream> 
#include <map>
using namespace std; 
int main()
{
    int a[10] = {1,2,3,2,1,3,2,4,1,1}; //Input array: hardcoded for testing
    map<int, int> m;

    for(int i=0;i<10;i++)
    {
        m[a[i]]++;  //Increment the value of key for counting occurances
    }

    int mostNumTimes = 0; 
    int number = -999; //-999 represents invalid number
    map<int,int>::iterator it = m.begin();
    for( ;it != m.end(); it++)  //Find the number which occurred 
    {                           //most number of times
        if(it->second > mostNumTimes)
        {
            mostNumTimes = it->second;
            number = it->first;
        }
    }
    if(number != -999)   //Print number and number of times it occurred
    {
        cout<<"Number: "<<number<<endl;
        cout<<"Number of times occured: "<<mostNumTimes<<endl;
    }
    else
    {
        cout<<"Input array is empty"<<endl;
    }
    return 0;
}

Output:

Number: 1

Number of times occured: 4

Question: Are there any optimal ways of doing it ? In the end, i am iterating through entire map as I couldn't find any member function for finding key whose value is highest in map. can i avoid iterating all keys ?

Note: I am not considering if multiple numbers occuring same number of times. I am finding first number with most occurances.

Answer 1

You could maintain a current max (count and int value) as you iterate the values. On each increment in the map, you could update the values so you don't have to iterate at the end.

map<int, int> m;
int currentMax = -999;
int maxCount = 0;
for(int i=0;i<10;i++)
{
    int updated = m[a[i]]++;  //Increment the value of key for counting occurances        
    updated++; // due to post increment 
    if (maxCount < updated) {
         maxCount = updated;
         currentMax = i;
    }
}

Because this is an entertaining exercise, it seems we're all assuming that map iteration is cheap. While iterating a map is also O(N), it's much more expensive than iterating over a vector or array. So what's cheaper, iterating a possibly reduced size map, or doing a really basic if check that will trigger two assignments at some percentage? Both your solution and this one are O(N) assuming you change to use an unordered map. Right now you're not, so each insert is log(n) and actually I think switching to an unordered map will be your biggest gain at this point.