Find Index of Maximum Occurring Element with Equal Probability

Given a collection of integers, develop an algorithm to find the index of maximum occurring element with equal probability.


 
For example, consider the input: {4, 3, 6, 8, 4, 6, 2, 4, 5, 9, 7, 4}. The maximum occurring element, which happens to be 4, occurs at index 0, 4, 7 and 11. The solution should return any one of these indices with the equal probability.
 

 
The problem looks complex at first look but has very simple solution. Below is the algorithm:
 

  1. Store the count of each element of the input in a map.
     
  2. Traverse the map and find the maximum occurring element.
     
  3. Generate a random number k between 1 and the count of maximum occurring element.
     
  4. Traverse the input and return index of the k’th occurrence of maximum occurring element.

 
Below is C++ implementation of the algorithm:

 

Download   Run Code

Output (will vary):

Index of maximum occurring element: 11
Index of maximum occurring element: 4
Index of maximum occurring element: 7
Index of maximum occurring element: 7
Index of maximum occurring element: 11

 
The time complexity of the proposed solution is O(n) and requires O(n) extra space for std::unordered_map.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz