1157. Online Majority Element In Subarray
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class MajorityChecker {
private:
    unordered_map<int, vector<int>> positions;
    vector<int> arr;

public:
    MajorityChecker(vector<int>& arr) : arr(arr) {
        for (int i = 0; i < arr.size(); ++i)
            positions[arr[i]].push_back(i);
    }
    
    int query(int left, int right, int threshold) {
        int candidate = -1;
        for (int i = 0; i < 20; ++i) {
            int randomIndex = left + rand() % (right - left + 1);
            int num = arr[randomIndex];
            auto& pos = positions[num];
            int l = lower_bound(pos.begin(), pos.end(), left) - pos.begin();
            int r = upper_bound(pos.begin(), pos.end(), right) - pos.begin();
            if (r - l >= threshold) return num;
        }
        return -1;
    }
};

```
['C++']