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

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;
    }
}