Java Segment Tree + Moore's Voting + Binary Search
I could not find a Java solution so I tried to wrtie it myself based on the same idea as this brilliant post https://leetcode.com/problems/online-majority-eleme
I could not find a Java solution so I tried to wrtie it myself based on the same idea as this brilliant post https://leetcode.com/problems/online-majority-element-in-subarray/discuss/360493/Python-Segment-tree-(merge-in-O(1)-query-O(log-n))\n```\nclass MajorityChecker {\n    private int[] arr;\n    private int n;\n    private int[][] segmentTree;\n    private Map<Integer, List<Integer>> map;\n\n    public MajorityChecker(int[] arr) {\n        n = arr.length;\n        if(n > 0){\n            this.arr = arr;\n            int x = (int)Math.ceil(Math.log(n)/Math.log(2));\n            int size = 2 * (int)Math.pow(2, x) - 1;\n            segmentTree = new int[size][2];\n            build(0, n - 1, 0);\n            map = new HashMap<>();\n            for(int i = 0; i < arr.length; i++){\n                map.putIfAbsent(arr[i], new ArrayList<>());\n                map.get(arr[i]).add(i);\n            }\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int[] cand = queryUtil(0, n - 1, left, right, 0);\n        if(cand[1] == 0){\n            return -1;\n        }\n        List<Integer> list = map.get(cand[0]);\n        int l = searchLeft(list, left);\n        int r = searchRight(list, right);\n        return r - l + 1 >= threshold ? cand[0] : -1;\n    }\n    \n    private int searchLeft(List<Integer> lst, int t){\n        int l = 0;\n        int r = lst.size() - 1;\n        while(l < r){\n            int mid = l + (r - l) / 2;\n            if(lst.get(mid) < t){\n                l = mid + 1;\n            }else{\n                r = mid;\n            }\n        }\n        return l;\n    }\n    \n    private int searchRight(List<Integer> lst, int t){\n        int l = 0;\n        int r = lst.size() - 1;\n        while(l < r){\n            int mid = l + (r - l + 1) / 2;\n            if(lst.get(mid) > t){\n                r = mid - 1;\n            }else{\n                l = mid;\n            }\n        }\n        return l;\n    }\n    \n    private void build(int start, int end, int index){\n        if(start == end){\n            segmentTree[index] = new int[]{arr[start], 1};\n            return;\n        }\n        int mid = start + (end - start) / 2;\n        build(start, mid, 2 * index + 1);\n        build(mid + 1, end, 2 * index + 2);\n        segmentTree[index] = merge(segmentTree[2 * index + 1], segmentTree[2 * index + 2]);\n    }\n    \n    private int[] merge(int[] a, int[] b){\n        if(a[0] == b[0]){\n            return new int[]{a[0], a[1] + b[1]};\n        }\n        if(a[1] > b[1]){\n            return new int[]{a[0], a[1] - b[1]};\n        }\n        return new int[]{b[0], b[1] - a[1]};\n    }\n    \n    private int[] queryUtil(int start, int end, int left, int right, int index){\n        if(left > end || right < start){\n            return new int[]{0, 0};\n        }\n        if(left <= start && right >= end){\n            return segmentTree[index];\n        }\n        int mid = start + (end - start) / 2;\n        int[] a = queryUtil(start, mid, left, right, 2 * index + 1);\n        int[] b = queryUtil(mid + 1, end, left, right, 2 * index + 2);\n        return merge(a, b);\n    }\n}\n```
[]