# Question - 8

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`

```java
class MajorityChecker {
    // A treeNode stores the majority element, with it's count
    // for a given range
    static class Pair {
        int element, count;

        Pair(int element, int count) {
            this.element = element;
            this.count = count;
        }
    }

    int[] arr;
    Pair[] tree;
    // Map of Elements -> TreeSet of their indices
    // This is used for finding the occourence of an element in a given range in O(logN)
    Map<Integer, TreeSet<int[]>> map = new HashMap<>();

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        tree = new Pair[4 * arr.length];
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], k -> new TreeSet<>((a, b) -> a[0] - b[0]));
            map.get(arr[i]).add(new int[] { i, map.get(arr[i]).size() });
        }
        // NlogN process
        buildTree(0, arr.length - 1, 1);
    }

    public void buildTree(int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], 1);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(start, mid, 2 * index);
        buildTree(mid + 1, end, 2 * index + 1);
        Pair left = tree[2 * index], right = tree[2 * index + 1];
        int leftCount = 0, rightCount = 0;
        if (left.element != -1)
            leftCount = map.get(left.element).floor(new int[] { end, 0 })[1]
                    - map.get(left.element).ceiling(new int[] { start, 0 })[1] + 1;
        if (right.element != -1)
            rightCount = map.get(right.element).floor(new int[] { end, 0 })[1]
                    - map.get(right.element).ceiling(new int[] { start, 0 })[1] + 1;
        if (leftCount * 2 > end - start + 1)
            tree[index] = new Pair(left.element, leftCount);
        else if (rightCount * 2 > end - start + 1)
            tree[index] = new Pair(right.element, rightCount);
        else
            tree[index] = new Pair(-1, 0);
    }

    public int query(int left, int right, int threshold) {
        // LogN*LogN
        Pair majority = findMajority(0, arr.length - 1, 1, left, right);
        if (majority.count >= threshold)
            return majority.element;
        return -1;
    }

    public Pair findMajority(int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(-1, 0);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair left = findMajority(start, mid, 2 * index, L, R);
        Pair right = findMajority(mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(-1, 0);
        int leftCount = 0, rightCount = 0;
        int limit1 = Math.max(L, start), limit2 = Math.min(R, end);
        if (left.element != -1)
            leftCount = map.get(left.element).floor(new int[] { limit2, 0 })[1]
                    - map.get(left.element).ceiling(new int[] { limit1, 0 })[1] + 1;
        if (right.element != -1)
            rightCount = map.get(right.element).floor(new int[] { limit2, 0 })[1]
                    - map.get(right.element).ceiling(new int[] { limit1, 0 })[1] + 1;
        if (leftCount * 2 > limit2 - limit1 + 1)
            ans = new Pair(left.element, leftCount);
        else if (rightCount * 2 > limit2 - limit1 + 1)
            ans = new Pair(right.element, rightCount);
        return ans;
    }
}
```
