Binary Search and Random Sampling
Intuition\nBy randomly sampling elements in the range, we take advantage of the fact that if a majority element exists, there is a high chance (50% per sample) 
# Intuition\nBy randomly sampling elements in the range, we take advantage of the fact that if a majority element exists, there is a high chance (50% per sample) of selecting it. The probability of not selecting the majority element after 8 random samples is \\($$ \\frac{1}{2^8}$$\\), which is a very low chance (~0.004%). This makes the approach sufficiently reliable for the purpose of this problem.\n\n\n# Approach\n1. **Initialization**:\n   - Preprocess the array to store the indices of each element in an array `self.occ`. This allows us to use binary search for efficiently finding how many times an element appears in any given subarray.\n   \n2. **Querying**:\n   - For each query, randomly select 8 indices in the range `[left, right]`.\n   - For each selected index, find the corresponding element and determine its frequency in the subarray using `bisect_left` and `bisect_right` to get the bounds for the element\'s occurrences.\n   - If the frequency of any randomly selected element meets or exceeds the `threshold`, return it.\n   - If no majority element is found after the 8 random samples, return `-1`.\n\n# Complexity\n- **Time complexity**:\n  - The preprocessing step (building `self.occ`) takes $$O(n)$$, where `n` is the length of the array.\n  - Each query runs up to 8 random samples and uses binary search (`bisect_left` and `bisect_right`), each taking $$O(\\log n)$$. Therefore, the time complexity for each query is $$O(8 \\log n)$$, which simplifies to $$O(\\log n)$$.\n\n- **Space complexity**:\n  - The space complexity is $$O(n)$$ for storing the array `self.occ`, where `n` is the number of elements in the input array.\n\n\n# Code\n```python3 []\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        n = len(arr)\n        self.arr = arr\n        self.occ = [[] for _ in range(max(arr) + 1)]\n        for i in range(n):\n            self.occ[arr[i]].append(i)\n            \n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        for i in range(8):\n            rand = random.randint(left, right)\n            check = self.arr[rand]\n            leftind = bisect.bisect_left(self.occ[check], left)\n            rightind = bisect.bisect_right(self.occ[check], right)\n            if rightind - leftind >= threshold:\n                return check\n        return -1\n        \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```
['Binary Search', 'Design', 'Python3']