Python sol by dict and bisect. 85%+ [w/ Hint]
Python sol by dict and bisect.\n\n---\n\nHint:\n\nFirst, build a dictionary to store the indices for each number\n\nSecond, create a list that store the number,
Python sol by dict and bisect.\n\n---\n\n**Hint**:\n\nFirst, build a dictionary to store the indices for each number\n\nSecond, create a list that store the number, sorted by occurrences in descending order\n\nThird, iterate the number from high occurrence to low occurrence,\nthen use bisection to check occurrence of current number satisfies threshold or not\n\n---\n\n**Implementation**:\n\n```\n\nfrom collections import defaultdict\nfrom bisect import bisect_left, bisect_right\n\nclass MajorityChecker:\n    def __init__(self, arr):\n        \n        # key   : number\n        # value : list of indices for number\n        self.num_idx_dict = defaultdict( list )\n        \n        # Append index to corresoinding number\'s dictionary\n        for idx, number in enumerate( arr ):\n            \n            self.num_idx_dict[ number ].append( idx )\n        \n        # With descending order of number of occurrences\n        self.candidates = sorted( self.num_idx_dict, key = lambda x: len(self.num_idx_dict[x]), reverse = True)\n\n        \n    def query(self, left, right, threshold):\n        \n        for number in self.candidates:\n            \n            # Longest occurrences is smaller than threhsold, then no solution\n            if len( self.num_idx_dict[number] ) < threshold:\n                return -1\n            \n            left_idx = bisect_left( self.num_idx_dict[number], left)\n            right_idx = bisect_right( self.num_idx_dict[number], right)\n            \n            if right_idx - left_idx >= threshold:\n                return number\n            \n        return -1\n```
['Sorting', 'Python', 'Python3']