NumPy 4-5 lines
Accepted in 1780 ms. Five lines if you count the import.\n\nimport numpy as np\n\nclass MajorityChecker:\n    def __init__(self, arr):\n        self.a = np.arra
Accepted in 1780 ms. Five lines if you count the import.\n```\nimport numpy as np\n\nclass MajorityChecker:\n    def __init__(self, arr):\n        self.a = np.array(arr)\n\n    def query(self, left, right, threshold):\n        c = np.bincount(self.a[left:right+1])\n        x = np.argmax(c)\n        return x if c[x] >= threshold else -1\n```\nI also came up with a more efficient solution but then saw that lee215 had already posted a virtually identical one:\n```\nclass MajorityChecker:\n\n    def __init__(self, A):\n        self.A = A\n        self.indexes = collections.defaultdict(list)\n        for i, a in enumerate(A):\n            self.indexes[a].append(i)\n\n    def query(self, left, right, threshold):\n        for _ in range(30):\n            a = self.A[random.randint(left, right)]\n            indexes = self.indexes[a]\n            lo = bisect.bisect_left(indexes, left)\n            hi = bisect.bisect(indexes, right)\n            if hi - lo >= threshold:\n                return a\n        return -1\n```
[]