Online Majority Element In Subarray

Problem statement

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]ExplanationMajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);majorityChecker.query(0, 5, 4); // return 1majorityChecker.query(0, 3, 3); // return -1majorityChecker.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.

My solution

/**
 * @param {number[]} arr
 */
var MajorityChecker = function(arr) {
    this.list = [...arr];
};

/** 
 * @param {number} left 
 * @param {number} right 
 * @param {number} threshold
 * @return {number}
 */
MajorityChecker.prototype.query = function(left, right, threshold) {
    const map = new Map();
    for (let i = left; i <= right; i++) {
        const curr = this.list[i]
        if (!map.has(curr)) {
            map.set(curr, 0)
        }
        map.set(curr, map.get(curr) + 1)
    }
    
    for (const [key, value] of map.entries()) {
        if (value >= threshold) {
            return key
        }
    }
    
    // console.log(map, left, right, threshold)
    return -1
};

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