Online Majority Element In Subarray

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:

class MajorityChecker {
    private SegmentTreeNode treeRoot;
    private Map<Integer, List<Integer>> idxMap;

    public MajorityChecker(int[] nums) {
        this.idxMap = new HashMap<>();
        this.treeRoot = buildTree(0, nums.length - 1, nums);

        for (int i = 0; i < nums.length; ++i) {
            List<Integer> idxList = idxMap.computeIfAbsent(nums[i], k -> new ArrayList<>());
            idxList.add(i);
        }
    }

    public int query(int left, int right, int threshold) {
        Pair cand = queryTree(treeRoot, left, right);
        if (cand.freq >= threshold) {
            return cand.val;
        }

        // According to Java Collections.binarySearch API:
        // if key doesn't exist in the list, will return: -(insertion point) - 1
        int leftIdx = Collections.binarySearch(idxMap.get(cand.val), left);
        if (leftIdx < 0) {
            leftIdx = -leftIdx - 1;
        }

        int rightIdx = Collections.binarySearch(idxMap.get(cand.val), right);
        if (rightIdx < 0) {
            rightIdx = -rightIdx - 2;
        }

        if (rightIdx - leftIdx + 1 >= threshold) {
            return cand.val;
        }

        return -1;
    }

    //////////////////////////////////////////////
    // following code is SegmentTree related stuff
    private SegmentTreeNode buildTree(int start, int end, int[] nums) {
        if (start == end) {
            return new SegmentTreeNode(start, end, new Pair(nums[start], 1));
        }

        SegmentTreeNode root = new SegmentTreeNode(start, end, null);

        int mid = start + (end - start) / 2;
        root.left = buildTree(start, mid, nums);
        root.right = buildTree(mid + 1, end, nums);
        root.pair = mergePair(root.left.pair, root.right.pair);

        return root;
    }

    private Pair queryTree(SegmentTreeNode root, int start, int end) {
        // System.out.println(root.start + ", " + root.end + ", " + start + ", " + end);
        if (start <= root.start && root.end <= end) {
            return root.pair;
        }

        Pair res = new Pair(0, 0);
        int mid = root.start + (root.end - root.start) / 2;
        if (start <= mid) {
            res = mergePair(res, queryTree(root.left, start, end));
        }
        if (mid < end) {
            res = mergePair(res, queryTree(root.right, start, end));
        }

        return res;
    }

    private Pair mergePair(Pair pair1, Pair pair2) {
        if (pair1.val == pair2.val) {
            return new Pair(pair1.val, pair1.freq + pair2.freq);
        }

        if (pair1.freq > pair2.freq) {
            return new Pair(pair1.val, pair1.freq - pair2.freq);
        }

        return new Pair(pair2.val, pair2.freq - pair1.freq);
    }

    static class SegmentTreeNode {
        int start;
        int end;
        Pair pair;
        SegmentTreeNode left;
        SegmentTreeNode right;

        SegmentTreeNode(int start, int end, Pair pair) {
            this.start = start;
            this.end = end;
            this.pair = pair;
            this.left = null;
            this.right = null;
        }
    }

    static class Pair {
        int val;
        int freq;

        Pair(int val, int freq) {
            this.val = val;
            this.freq = freq;
        }
    }

}

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