[Python] Clear and well-commented segment tree solution, accepted
I am posting my segment-tree based solution. The code is heavily commented inline to be as clear as possible. The main idea, or the optimal substructure is, to 
I am posting my segment-tree based solution. The code is heavily commented inline to be as clear as possible. The main idea, or the optimal substructure is, to find the majority element over an inclusive range of [low, high], you can partition the range into two parts and find the majority element over each. If there does not exist a majority element in neither the left partition nor the right partition, then there is no majority element (See proof in the code comment). If the majority element from the left partition is x and the majority element from the right partition is y, and x == y, then the majority element over the whole range must be x. If x != y, then you must check if either x or y is the majority element over the whole range (by verifying that `frequency(x or y) * 2 >  high - low + 1`). Notice in either case, you are only verifying no more than 2 possible candidate values. Once you have the majority element over the whole range, the only thing left is verifying that its frequency is >= `threshold`.\n\n```\nclass MajorityChecker(object):\n\n    def __init__(self, arr):\n        """\n        :type arr: List[int]\n        """\n        # For every unique val in arr, note its indexes in arr in ascending index order.\n        # e.g. arr = [1, 1, 2, 2, 1, 1], then\n        # _idx_by_val = {1: [0, 1, 4, 5], 2: [2, 3]}\n        # Such a data structure is useful when we need to figure out how many\n        # instances of \'1\' exists between some inclusive range [low, high], by\n        # binary-searching for low and high over the list _idx_by_val[1].\n        # see _get_frequency() function below.\n        self._idx_by_val = collections.defaultdict(list)\n        for i in range(len(arr)):\n            self._idx_by_val[arr[i]].append(i)\n        self._root = self._build_segment_tree_node(0, len(arr) - 1, arr)\n\n    def query(self, left, right, threshold):\n        """\n        :type left: int\n        :type right: int\n        :type threshold: int\n        :rtype: int\n        """\n        segment = (left, right)\n        maj = self._query_segment_tree(self._root, segment)\n        if maj != None and self._get_frequency(maj, left, right) >= threshold:\n            return maj\n        \n        return -1\n    \n    # Construct the segment node such that node.maj, if not None, holds the\n    # majority element in arr[low..high]\n    def _build_segment_tree_node(self, low, high, arr):\n        node = MajorityChecker.Node(low, high)\n        if low == high:\n            node.maj = arr[low]\n            return node\n        \n        mid = (low + high) / 2\n        node.left = self._build_segment_tree_node(low, mid, arr)\n        node.right = self._build_segment_tree_node(mid + 1, high, arr)\n        # If both the left and right side have the same majority element, the majority\n        # element over the entire range must be that element as well\n        if node.left.maj == node.right.maj:\n            node.maj = node.left.maj\n            return node\n        \n        # If there\'s no clear majority, then whichever side\'s majority element that\n        # happens to be the majority element of the entire range is the real majority.\n        nb_elts = high - low + 1\n        if node.left.maj != None and self._get_frequency(node.left.maj, low, high) * 2 > nb_elts:\n            node.maj = node.left.maj\n        if node.right.maj != None and self._get_frequency(node.right.maj, low, high) * 2 > nb_elts:\n            node.maj = node.right.maj\n                \n        # Since we only checked the frequencies of the node.left.maj and node.right.maj, could we \n        # possibly have missed the element y, y != node.left.maj and y != node.right.maj, such\n        # that y is actually the majority over the entire range?\n        # If y is NOT the majority of the left nor right side,  then (I am using |..| to indicate frequency):\n        #    |y in [low, mid]| * 2 <= mid - low + 1 and |y in [mid+1, high]| <= high - (mid + 1) + 1\n        # => |y in [low, mid]| + |y in [mid+1, high]| <= high - (mid + 1) + 1 + mid - low + 1\n        # => |y in [low, high]| <= high - low + 1\n        # => y cannot be the majority element\n        return node\n\n    # Given some segment [left, right], find the majority element in arr[left..right]\n    def _query_segment_tree(self, node, segment):\n        if segment[0] == node.low and segment[1] == node.high:\n            return node.maj\n        \n        node_mid = (node.low + node.high) / 2\n        \n        left_segment = [max(node.low, segment[0]), min(segment[1], node_mid)]\n        left_maj = None\n        if left_segment[0] <= left_segment[1]:\n            left_maj = self._query_segment_tree(node.left, left_segment)\n\n        right_segment = [max(node_mid + 1, segment[0]), segment[1]]\n        right_maj = None\n        if right_segment[0] <= right_segment[1]:\n            right_maj = self._query_segment_tree(node.right, right_segment)\n        \n        # If element x is the majority of both the left and right partition, it must, in total,\n        # occur more than half of the times amongst the entire range [node.low, node.high]\n        # and therefore the majority.\n        if left_maj == right_maj:\n            return left_maj\n        \n        # If there\'s no clear majority, then whichever side\'s majority element that\n        # happens to be the majority element of the entire range is the real majority.\n\n        nb_elts_in_segment = segment[1] - segment[0] + 1\n        if self._get_frequency(left_maj, segment[0], segment[1]) * 2 > nb_elts_in_segment:\n            return left_maj\n        \n        if self._get_frequency(right_maj, segment[0], segment[1]) * 2 > nb_elts_in_segment:\n            return right_maj\n        \n        # Duplicated comments here for clarity\n        # Since we only checked the frequencies of the left_maj and right_maj, could we \n        # possibly have missed the element y, y != left_maj and y != right_maj, that\'s \n        # the real majority over the entire range?\n        # If y is NOT the majority of the left nor right side, then (I am using |..| to indicate frequency):\n        #    |y in [low, mid]| * 2 <= mid - low + 1 and |y in [mid+1, high]| <= high - (mid + 1) + 1\n        # => |y in [low, mid]| + |y in [mid+1, high]| <= high - (mid + 1) + 1 + mid - low + 1\n        # => |y in [low, high]| <= high - low + 1\n        # => y cannot be the majority element\n\n        return None\n    \n    # How many instances of val is there in arr[low..high]?\n    def _get_frequency(self, val, low, high):\n        # For any i in [0..len(indexes) - 1], arr[indexes[i]] == val\n        # i.e. indexes holds the indices into arr where val is found\n        indexes = self._idx_by_val[val]\n        \n        # Find the smallest index, indexes[i], such that indexes[i] >= low and\n        # arr[indexes[i]] == val. Since _get_frequency() is only called\n        # when we know at least one instance of val exists in arr[low .. high],\n        # i is guaranteed to be valid. e.g. if indexes = [0, 1, 4, 6], low = 3 then i = 2\n        i = bisect.bisect_left(indexes, low)\n        \n        # Find the smallest index, indexes[j], such that indexes[j] <= high and\n        # arr[indexes[j]] == val. Note however it\'s possible to be given some `high`\n        # value such that indexes[-1] < high or, arr[high] != val but arr[high-1] == val.\n        # e.g. given indexes = [0, 1, 4, 6]\n        #      if high = 7 then j = 4;\n        #      if high = 5 then j = 3;\n        # In either case, we need to move j left by one\n        j = bisect.bisect_left(indexes, high)\n        if j == len(indexes) or indexes[j] != high:\n            j -= 1\n        return j - i + 1\n    \n    # Every node in segment tree represents a range [low, high] such that the majority\n    # element, if it exists, is self.maj. (Otherwise it is None indicating no majority\n    # element exists)\n    class Node(object):\n        def __init__(self, low, high):\n            self.low = low\n            self.high = high\n            self.maj = None\n  \n```
[]