[Java] TreeMap + Binary Search Solution
\nclass MajorityChecker {\n    // TreeMap store the <num, index list> pair\n    // Time complexity: O(NlogN)\n    private TreeMap<Integer, List<Integer>> treeMa
```\nclass MajorityChecker {\n    // TreeMap store the <num, index list> pair\n    // Time complexity: O(NlogN)\n    private TreeMap<Integer, List<Integer>> treeMap;\n    public MajorityChecker(int[] arr) {\n        treeMap = new TreeMap<>();\n        for (int i = 0; i < arr.length; i++) {\n            List<Integer> list = treeMap.getOrDefault(arr[i], new ArrayList<>());\n            if (list.isEmpty()) {\n                treeMap.put(arr[i], list);\n            }\n            list.add(i);\n        }\n    }\n    // For each num, check its index list, whether the index of left and index of right >= threshold\n    // Time complexity: O(logN*logN)\n    public int query(int left, int right, int threshold) {\n        for (Map.Entry<Integer, List<Integer>> entry : treeMap.entrySet()) {\n            int idx = entry.getKey();\n            List<Integer> list = entry.getValue();\n            if (list.size() < threshold) continue;\n            int low = Collections.binarySearch(list, left);\n            int high = Collections.binarySearch(list, right);\n            // get the current position of left\n            if (low < 0) low = -low - 1;\n            // get the next position of right\n            if (high < 0) high = -high - 1;\n            else high = high + 1;\n            if (high - low >= threshold) return idx;\n        }\n        return -1;\n    }\n}\n```
[]