## Algorithm

Problem Name: 1157. Online Majority Element In Subarray

Design a data structure that efficiently finds the majority element of a given subarray.

The majority element of a subarray is an element that occurs `threshold` times or more in the subarray.

Implementing the `MajorityChecker` class:

• `MajorityChecker(int[] arr)` Initializes the instance of the class with the given array `arr`.
• `int query(int left, int right, int threshold)` returns the element in the subarray `arr[left...right]` that occurs at least `threshold` times, or `-1` if no such element exists.

Example 1:

```Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

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

Constraints:

• `1 <= arr.length <= 2 * 104`
• `1 <= arr[i] <= 2 * 104`
• `0 <= left <= right < arr.length`
• `threshold <= right - left + 1`
• `2 * threshold > right - left + 1`
• At most `104` calls will be made to `query`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MajorityChecker = function(arr) {
const map = new Map()
for (let i = 0; i  <  arr.length; i++) {
if (!map.has(arr[i])) map.set(arr[i], [i])
else map.get(arr[i]).push(i)
}
this.pos = map
this.arr = arr
}

function lbs(arr, val) {
let lo = 0
let hi = arr.length - 1
if (arr[0] >= val) return 0
else if (arr[hi] < val) return Infinity
let mid
while (hi - lo > 1) {
mid = (hi + lo) >> 1
if (arr[mid] === val) return mid
else if (arr[mid]  <  val) lo = mid
else if (arr[mid] > val) hi = mid
}
return hi
}

function rbs(arr, val) {
let lo = 0
let hi = arr.length - 1
if (arr[hi] <= val) return hi
else if (arr[lo] > val) return -Infinity
let mid
while (hi - lo > 1) {
mid = (hi + lo) >> 1
if (arr[mid] === val) return mid
else if (arr[mid] < val) lo = mid
else if (arr[mid] > val) hi = mid
}
return lo
}

MajorityChecker.prototype.query = function(left, right, threshold) {
const { arr, pos } = this
let c = 20
while (c--) {
const idx = left + Math.floor(Math.random() * (right - left + 1))
const sort = pos.get(arr[idx])
const lidx = lbs(sort, left)
const ridx = rbs(sort, right)
if (ridx - lidx + 1 >= threshold) return arr[idx]
}
return -1
}
``````
Copy The Code &

Input

cmd
["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]

Output

cmd
[null, 1, -1, 2]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class MajorityChecker:

def __init__(self, arr: List[int]):
self.dp = collections.defaultdict(list)
for i, v in enumerate(arr):
self.dp[v].append(i)
self.occur = sorted([(len(v), k) for k, v in self.dp.items()], reverse = True)

def query(self, left: int, right: int, threshold: int) -> int:
for o, v in self.occur:
if o < threshold: break
l = self.dp[v]
low = bisect.bisect_left(l, left)
high = bisect.bisect_right(l, right)
if high - low >= threshold:
return v
return -1
``````
Copy The Code &

Input

cmd
["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]

Output

cmd
[null, 1, -1, 2]