Dedicated to wisdompeak
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\n// range => Segment tree; if the array was also modified, then no other option;\n// need to quicklY: for i..j find most frequent elem and its count\n\n// KEY OBSERVATION: for each range there can be only 1 or 0 majority elems!\n\n// Boyer-moore majority voting algorithm! When we see X and candidateCnt = 0; set candidate = X\n// for each elem =X/!=X ++/--candidateCnt; guarantees to find the majority because if count falls to 0, the majority elem\n// will be met again in the future and will again become majority\n\n// Key to solution: given L...R and L..M,M..R inside intervals\n// if maj(L..M) = val1 and maj(M..R) = val2, then maj(L..R) = val1 OR val2; no other vals will have enough counts to\n// surpass ((R - L + 1) / 2) so they can\'t become majority\n\n// We notice, there is no way to directly solve the question of finding the majority elem with just Segment Tree!\n// Instead, we build the Segment Tree to give us the majority CANDIDATE within a range with the MOST VOTES!\n// When merging 2 subintervals, we prioritize the MORE DOMINANT CANDIDATE based on its original subinterval!\n// Finally, the DFS query(l,r) O(LogN) will give us the most probable candidate within a range, but no guarantee\n// that it is a majority elem at all! So how do we verify?\n\n// We built map[val] = [all indexes of val in the original array]\n// now we find LEFT and RIGHT from the query using binary search O(LogN)\n// and see the distance between them = number of times our most probable candidate actually appears in the range\n\n\n//    1\n//  1    3\n// [1, 3, 1]\n\n//             3\n//       3            2\n// [1,1,3,3,3    3,3,2,2,2]\n\n// example 3: no majority = X\n//         3\n//   X   X   X  3\n// [1,3 1,3 1,3 3]\n\nclass MajorityChecker {\n    int[] arr;\n    SegmentTreeNode root;\n    HashMap<Integer, List<Integer>> valToIds = new HashMap<>();\n\n    public MajorityChecker(int[] arr) {\n        this.arr = arr;\n        root = new SegmentTreeNode(0, arr.length - 1);\n    }\n\n    public int query(int left, int right, int threshold) {\n        int[] qRes = root.getMajorityCandidateInRange(left, right);\n        int majCandidate = qRes[0];\n        int majVotes = qRes[1];\n\n        // double check the freq of the candidate\n        int leftId = Collections.binarySearch(valToIds.get(majCandidate), left);\n        if (leftId < 0) leftId = ~leftId;\n        int rightId = Collections.binarySearch(valToIds.get(majCandidate), right);\n        if (rightId < 0) rightId = ~rightId - 1; // -1 because in JAVA it gives the ID of the first bigger elem!\n\n        if (rightId - leftId + 1 >= threshold) return majCandidate;\n        return -1;\n    }\n\n    class SegmentTreeNode {\n        int l, r, majVal, majVotes; // votes = relative frequency compared to all other elems\n        SegmentTreeNode left, right;\n\n        int[] getMajorityCandidateInRange(int low, int high) {\n            if (l > high || r < low) return null;\n            if (l >= low && r <= high) return new int[]{majVal, majVotes};\n\n            int[] leftQ = left.getMajorityCandidateInRange(low, high);\n            int[] rightQ = right.getMajorityCandidateInRange(low, high);\n            if (leftQ == null) return rightQ;\n            if (rightQ == null) return leftQ;\n            \n            if (leftQ[0] == rightQ[0]) {\n                leftQ[1] += rightQ[1];\n                return leftQ;\n            }\n            if (leftQ[1] > rightQ[1]) {\n                leftQ[1] -= rightQ[1];\n                return leftQ;\n            }\n\n            rightQ[1] -= leftQ[1];\n            return rightQ;\n        }\n\n        SegmentTreeNode(int l, int r) {\n            this.l = l;\n            this.r = r;\n            if (l == r) {\n                valToIds.computeIfAbsent(arr[l], list -> new ArrayList<>()).add(l);\n                majVal = arr[l];\n                majVotes = 1;\n            } else {\n                int mid = l + (r - l) / 2;\n                left = new SegmentTreeNode(l, mid);\n                right = new SegmentTreeNode(mid + 1, r);\n\n                if (left.majVal == right.majVal) {\n                    majVal = left.majVal;\n                    majVotes = left.majVotes + right.majVotes;\n                } else {\n                    if (left.majVotes > right.majVotes) {\n                        majVal = left.majVal;\n                        majVotes = left.majVotes - right.majVotes;\n                    } else {\n                        majVal = right.majVal;\n                        majVotes = right.majVotes - left.majVotes;\n                    }\n                }\n            }\n        }\n\n\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker obj = new MajorityChecker(arr);\n * int param_1 = obj.query(left,right,threshold);\n */\n```
['Java']