2 Python solutions: random pick vs segment tree
Personally I like the random pick more, as the segment tree is more pedagogical and not very intuitive. I tried lowering the trial number down and 7 still works
Personally I like the random pick more, as the segment tree is more pedagogical and not very intuitive. I tried lowering the trial number down and 7 still works to pass the online judge.\nFor the segment tree solution, there are no query size dependence issues. I mainly copy the code I wrote for another problem [307. Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/) and modified it.\n\n```\n# Random pick strategy\nclass MajorityChecker:\n    # A good strategy can be referenced from Leetcode 961. N-Repeated Element in Size 2N Array\n    # Given a range, we can randomly pick a number inside and ask if it is majority element by binary search its appearance index array\n    def __init__(self, arr: List[int]):\n        self.arr = arr\n        self.indices = {}\n        for i, num in enumerate(arr):\n            if num not in self.indices:\n                self.indices[num] = []\n            self.indices[num].append(i)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        for trial in range(7):\n            pick = random.randint(left, right)\n            l = bisect.bisect_left(self.indices[self.arr[pick]], left)\n            r = bisect.bisect_right(self.indices[self.arr[pick]], right)\n            if r - l >= threshold:\n                return self.arr[pick]\n        return -1\n\n\n# Your MajorityChecker object will be instantiated and called as such:\n# obj = MajorityChecker(arr)\n# param_1 = obj.query(left,right,threshold)\n\n# Segment tree solution\nclass MajorityChecker:\n    # Instead of using probabilities in our favour, we can also use the segment tree data structure in our favour.\n    # The idea is because we are looking for majority in a range, we can first store the excess count of the majority in a segment by an array: [majority element, excess]\n    # The manner of lookup is exactly the same as in a range sum question like Leetcode 307. Range Sum Query - Mutable\n    # To be safe on getting the correct answer, we still construct the count index table for binary search\n    def __init__(self, arr: List[int]):\n        # Prepare the indices arrays for binary search\n        self.indices = {}\n        for i, num in enumerate(arr):\n            if num not in self.indices:\n                self.indices[num] = []\n            self.indices[num].append(i)\n        \n        # Build segment tree\n        self.n = len(arr)\n        self.tree = [[-1,-1] for i in range(2*self.n)]\n        for i, num in enumerate(arr):\n            self.tree[self.n + i] = [num, 1]\n        for i in range(self.n - 1, 0, -1):\n            self.tree[i] = self.segment_merge(self.tree[2*i], self.tree[2*i+1])\n    \n    # Given two segments majority elements and excesses, decide which element is the majority for the whole range and the excess\n    def segment_merge(self, seg1, seg2):\n        ele1, excess1 = seg1\n        ele2, excess2 = seg2\n        if ele1 == ele2:\n            return [ele1, excess1 + excess2]\n        elif excess1 >= excess2:\n            return [ele1, excess1 - excess2]\n        else:\n            return [ele2, excess2 - excess1]\n    \n    def query(self, left: int, right: int, threshold: int) -> int:\n        i, j = left + self.n, right + self.n\n        # initialize: 0 not in arr and excess of 0\n        ans = [0, 0]\n        while i <= j:\n            if i % 2 == 1:\n                ans = self.segment_merge(ans, self.tree[i])\n                i += 1\n            if j % 2 == 0:\n                ans = self.segment_merge(ans, self.tree[j])\n                j -= 1\n            i //= 2\n            j //= 2\n        # Never got any merge\n        if ans[0] == 0:\n            return -1\n        l = bisect.bisect_left(self.indices[ans[0]], left)\n        r = bisect.bisect_right(self.indices[ans[0]], right)\n        if r - l >= threshold:\n            return ans[0]\n        return -1\n\n# Your MajorityChecker object will be instantiated and called as such:\n# obj = MajorityChecker(arr)\n# param_1 = obj.query(left,right,threshold)\n```
[]