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:

- Store the count of each element of the input in a map.

- Traverse the map and find the maximum occurring element.

- Generate a random number k between 1 and the count of maximum occurring element.

- Traverse the input and return index of the k’th occurrence of maximum occurring element.

Below is C++ implementation of the algorithm:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <vector> #include <unordered_map> #include <climits> #include <ctime> #include <cstdlib> #include <unistd.h> // for sleep() using namespace std; // Return index of maximum occurring element with equal probability int findIndex(vector<int> input) { // store count of each element present in the vector in an unordered_map unordered_map<int, int> count; for (int val: input) count[val]++; // traverse the unordered_map and find the maximum occurring element int max_occurring; for (auto pair: count) { if (count[max_occurring] < pair.second) max_occurring = pair.first; } // initialize srand with distinctive value and generate a random // number k between 1 and count of maximum occurring element srand(time(nullptr)); int k = (rand() % count[max_occurring]) + 1; // traverse the input vector and return index of the k'th occurrence // of maximum occurring element int index = 0; while (k && index < input.size()) { if (input.at(index) == max_occurring) k--; index++; } return index - 1; } // Find index of maximum occurring element with equal probability int main() { vector<int> input = { 4, 3, 6, 8, 4, 6, 2, 4, 5, 9, 7, 4 }; for (int i = 0; i < 5; i++) { sleep(2); cout << "Index of maximum occurring element: " << findIndex(input) << endl; } return 0; } |

`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