TWO accepted Python code, bisearch w/ early termination, Segment Tree. Both beat 100%
Due to the bias against Python, most acceptable solutions in Java and C++ get TLE in python, if not optimized carefully.\n\nHere I contribute two accepted Pytho
Due to the bias against Python, most acceptable solutions in Java and C++ get TLE in python, if not optimized carefully.\n\nHere I contribute two accepted Python codes. \n\n(1) Bisearch with early termination; we will start searching from the most frequent element and break the search if the current element under check appears less than threshold times in the whole array. Runs in ~500ms, beat 100%.\n\nActually this method is still O(n) in the worst case, where all elements are almost different (meaning each value is repeated for only a few times, for example, all value appears twice), and (left, right) parameters in query are quite close. As an example, if all values appear twice in the array and query in a range where end - start == 2, in the worst case we need to traverse all possible values in the array which is O(n) time, and each check is O(1) since there are only 2 positions to bisearch within. However seems Leetcode test data does not include such cases.\n\n```\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.arr = arr\n        self.positions = collections.defaultdict(list)\n        for i, n in enumerate(arr):\n            self.positions[n].append(i)\n        self.elems = sorted(list(self.positions.keys()), key = lambda x: len(self.positions[x]), reverse = True)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        for elem in self.elems:\n            l = bisect.bisect_left(self.positions[elem], left)\n            r = bisect.bisect_right(self.positions[elem], right)\n            if r - l >= threshold:\n                return elem\n            elif len(self.positions[elem]) < threshold:\n                break\n        return -1\n```\n\n(2) Segment Tree; we will keep the majority element by segment tree. Each query will query the segment tree to get the majority element in the range (left, right), and then run bisearch to decide if the frequency of appearance is greater than threthold or not.\nRuns in O(logn * logn) time since the worst case for querying a segment tree is recursively query O(logn) segments and each query takes O(logn) for bisearch. Constructor takes O(n) time for preprocessing. Runtime ~2000 ms, beat 100%.\n\n```\nclass SegmentTree:\n    \n    def __init__(self, start, end):\n        self.start = start\n        self.end = end\n        self._left = None\n        self._right = None\n        self.val = -sys.maxsize\n    \n    @property\n    def mid(self):\n        return (self.start + self.end) // 2\n    \n    @property\n    def left(self):\n        if not self._left:\n            self._left = SegmentTree(self.start, self.mid)\n        return self._left\n\n    @property\n    def right(self):\n        if not self._right:\n            self._right = SegmentTree(self.mid, self.end)\n        return self._right\n    \n    def query(self, left, right, arr, positions):\n        \n        def is_majority(elem):\n            l = bisect.bisect_left(positions[elem], left)\n            r = bisect.bisect_right(positions[elem], right - 1)\n            if 2 * (r - l) > right - left:\n                return True\n            return False\n        \n        if left >= right:\n            return -1\n        else:\n            res = -1\n            if left == self.start and right == self.end:\n                if left == right - 1:\n                    self.val = arr[left]\n                elif self.val == -sys.maxsize:\n                    elem1 = self.left.query(left, self.mid, arr, positions)\n                    elem2 = self.right.query(self.mid, right, arr, positions)\n                    if elem1 != -1 and is_majority(elem1):\n                        self.val = elem1\n                    elif elem2 != -1 and is_majority(elem2):\n                        self.val = elem2\n                    else:\n                        self.val = -1\n                res = self.val \n            else:\n                elem1 = self.left.query(left, min(right, self.mid), arr, positions)\n                elem2 = self.right.query(max(left, self.mid), right, arr, positions)\n                if elem1 != -1 and is_majority(elem1):\n                    res = elem1\n                elif elem2 != -1 and is_majority(elem2):\n                    res = elem2\n            \n            return res\n            \n\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.arr = arr\n        self.positions = collections.defaultdict(list)\n        for i, n in enumerate(arr):\n            self.positions[n].append(i)\n        self.ST = SegmentTree(0, len(self.arr))\n    \n    def query(self, left: int, right: int, threshold: int) -> int:\n        res = self.ST.query(left, right+1, self.arr, self.positions)\n    \n        l = bisect.bisect_left(self.positions[res], left)\n        r = bisect.bisect_right(self.positions[res], right)\n        \n        return res if r - l >= threshold else -1\n```
[]