# 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++/Java implementation of the algorithm:

## Java

Output (will vary):

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

The time complexity of the proposed solution is O(n) and requires O(n) extra space for std::unordered_map.     (1 votes, average: 5.00 out of 5) Loading... 