Python Binary Search with Sorted Occurrence List
Very similar to other solutions, but we can use a sorted list that keeps the occurance of all elements, so we only interate through those with higher occurance.
Very similar to other solutions, but we can use a sorted list that keeps the occurance of all elements, so we only interate through those with higher occurance. It runs much faster. \n\n```\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.dp = collections.defaultdict(list)\n        for i, v in enumerate(arr):\n            self.dp[v].append(i)\n        self.occur = sorted([(len(v), k) for k, v in self.dp.items()], reverse = True)\n        \n    def query(self, left: int, right: int, threshold: int) -> int:\n        for o, v in self.occur:\n            if o < threshold: break\n            l = self.dp[v]\n            low = bisect.bisect_left(l, left)\n            high = bisect.bisect_right(l, right)\n            if high - low >= threshold:\n                return v\n        return -1\n```
[]