[C++] O(sqrt(N)*log(N)) with explaination
I think this question requires us to do some trade-off between checking the subarray directly (better for short subarray) and checking the occurrence of integer
I think this question requires us to do some trade-off between checking the subarray directly (better for short subarray) and checking the occurrence of integers (better for long subarray). We can set a ```shard``` to determine whether an subarray is short or long:\n\n```i.  right-left+1 <= shard```\n    In this case, we just go through the subarray ```arr[left:right+1]```, and find its majority. The time cost is ```O(right-left) <= O(shard)```.\n\t\n```ii. right-left+1 > shard```\n    In this case, we know ```threshold > shard/2```, so we can check all the integers that occur at least ```threshold``` times. For each integer, we check whether it occurs at least ```threshold``` times in the subarray ```arr[left:right+1]``` by using an ordered "pre-count" structure. This operation takes ```O(logN)``` time for a single integer, and ```O(N/shard*logN)``` time for function ```query()``` (because there are at most ```N/k``` integers that occur at least ```k``` times).\n        \nThen, our total runtime is ```O(max(shard, N/shard*logN))```. We can choose an appropriate ```shard``` to get optimized solution. In the following code, I use ```shard=sqrt(N)```, and the total time cost is ```O(N*log(N))``` for ```MajorityChecker()```, ```O(sqrt(N)*log(N))``` for ```query()```. The total space is ```O(N)```.\n\n\n```C++\nclass MajorityChecker {\n    vector<int> arr;\n    int shard;\n    \n    unordered_map<int, map<int, int>> precnt;\n    vector<int> nums;\npublic:\n    MajorityChecker(vector<int>& arr) {\n        this->arr = arr;\n        shard = sqrt(arr.size());\n        \n        // Initialize pre-count\n        for (int i=0; i<arr.size(); i++) {\n            auto &pc = precnt[arr[i]];\n            if (pc.empty()) pc[-1] = 0;\n            pc[i] = pc.rbegin()->second + 1;\n        }\n        \n        // Sort all integers by the times of occurrence (descending)\n        for (auto &pc : precnt) nums.push_back(pc.first);\n        sort(nums.begin(), nums.end(), [&] (const int &a, const int &b) {\n            return precnt[a].size() > precnt[b].size();\n        });\n    }\n    \n    int query(int left, int right, int threshold) {\n        if (right - left + 1 > shard) {\n            // For long range, check the integers with most occurrence.\n            for (int n : nums) {\n                int occurrence = precnt[n].rbegin()->second;\n                if (occurrence < threshold) break;\n                int nl = prev(precnt[n].lower_bound(left))->second;\n                int nr = prev(precnt[n].upper_bound(right))->second;\n                if (nr - nl >= threshold) return n;\n            }\n            return -1;\n        } else {\n            // For short range, just go through the subarray.\n            unordered_map<int, int> cnt;\n            for (int i=left; i<=right; i++) {\n                cnt[arr[i]] ++;\n                if (cnt[arr[i]] >= threshold) return arr[i];\n            }\n            return -1;\n        }\n    }\n};\n ```
[]