Python bucket solution, concise
\n# Approach\nThis is the python implementation of the bucket solution that everyone has discussed and shared. \n\n# Complexity\n- Time complexity:\n Add your t
\n# Approach\nThis is the python implementation of the bucket solution that everyone has discussed and shared. \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```\nfrom bisect import *\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        a2i = collections.defaultdict(list)\n        for i, n in enumerate(arr):\n            a2i[n].append(i)\n        self.arr, self.a2i = arr, a2i\n        self.n_buckets = len(arr) ** 0.5\n        self.buckets = [x for x in a2i.keys() if len(a2i[x]) >= len(arr) ** 0.5]\n\n    def vote(self, l, r): // this is just classic "Boyer\u2013Moore majority vote algorithm" implementation\n        m, c = self.arr[l], 1\n        f = Counter()\n        f[m] += 1\n        for i in range(l + 1, r + 1):\n            f[self.arr[i]] += 1\n            if self.arr[i] == m:\n                c += 1\n            elif self.arr[i] != m:\n                if c > 1:\n                    c -= 1\n                else:\n                    m = self.arr[i]\n                    c = 1\n        return m, f[m]\n\n    def find(self, x, l, r): // binary search for a specific element frequency\n        arr = self.a2i[x]\n        i = bisect_left(arr, l)\n        j = bisect_right(arr, r)\n        return j - i\n\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        if (threshold >= self.n_buckets):\n            for x in self.buckets:\n                if self.find(x, left, right) >= threshold:\n                    return x\n            return -1\n        else:\n            x, f = self.vote(left, right)\n            if x != -1 and f >= threshold:\n                return x\n            else:\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```
['Python', 'Python3']