Formatted question description: https://leetcode.ca/all/1157.html

# 1157. Online Majority Element In Subarray

Hard

## Description

Implementing the class MajorityChecker, which has the following API:

• MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
• int query(int left, int right, int threshold) has arguments such that:
• 0 <= left <= right < arr.length representing a subarray of arr;
• 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2


Constraints:

• 1 <= arr.length <= 20000
• 1 <= arr[i] <= 20000
• For each query, 0 <= left <= right < len(arr)
• For each query, 2 * threshold > right - left + 1
• The number of queries is at most 10000

## Solution

Maintain an array in the class. For the constructor, simply assign the array to the array in the class. For method query, since the elements are in the range [1, 20000], create an array count of length 20001, and loop over the array from index left to index right. If at one point, a number’s count reaches threshold, then return the number. If no such number is met, return -1.

class MajorityChecker {
int[] arr;

public MajorityChecker(int[] arr) {
this.arr = arr;
}

public int query(int left, int right, int threshold) {
int[] count = new int;
for (int i = left; i <= right; i++) {
int num = arr[i];
if (++count[num] == threshold)
return num;
}
return -1;
}
}

/**
* Your MajorityChecker object will be instantiated and called as such:
* MajorityChecker obj = new MajorityChecker(arr);
* int param_1 = obj.query(left,right,threshold);
*/