Simple solution using random sampling
The idea is to pre-process the array into a map of positions where the keys are the values and they point to the vector of positions where they occur. Let\'s ca
The idea is to pre-process the array into a map of positions where the keys are the values and they point to the vector of positions where they occur. Let\'s call this the position_map   (unordered_map<int, vector<int>>)\n\nDuring queries, we randomly query 100 positions within [left, right] , find the elements found there, sort them on number of occurrences in sample.  And then for each element, use binary search (upper_bound(right) - lower_bound(left)) to figure out the number of occurrences in position_map[element]. If any of the elements from the sample pass the threshold, return the elem. Else return -1.\n\nWe would never give an incorrect element as the majority element with this majority. And if a majority element exists, we would find it with 1 - (1/2)^100 probability.\n\n```\nclass MajorityChecker {\npublic:\n    unordered_map<int, vector<int>> positions;\n    vector<int> arr;\n    MajorityChecker(vector<int>& arr) {\n        srand (time(NULL));\n        this->arr = arr;\n        for (int i = 0; i < arr.size(); i++)\n            positions[arr[i]].push_back(i);\n    }\n    \n    int query(int left, int right, int threshold) {\n        std::default_random_engine generator;\n        std::uniform_int_distribution<int> distribution(left, right);\n        unordered_map<int, int> elems_to_check;\n        for (int i = 0; i < 100 ; i++)\n            elems_to_check[arr[distribution(generator)]]++;\n\t\t\t\n        vector<pair<int,int>> elems_to_check1;\n        for (const auto& elem : elems_to_check)\n            elems_to_check1.push_back({elem.second, elem.first});\n\t\t\t\n        sort(elems_to_check1.begin(), elems_to_check1.end());\n        vector<int> elems;\n        for (const auto& elem : elems_to_check1)\n            elems.push_back(elem.second);\n\t\t\t\n        //cout << endl;\n        for (const auto& elem : elems) {\n            int val = upper_bound(positions[elem].begin(), positions[elem].end(), right) - lower_bound(positions[elem].begin(), positions[elem].end(), left);\n            //cout << left << " " << right << " " << elem << " " << val << endl;\n            if (val >= threshold)\n                return elem;\n        }\n        return -1;\n    }\n};\n\n```
[]