1157. Online Majority Element In Subarray

Description

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.

 

Solutions

Solution: Binary Search

• Time complexity: O(20logn)
• Space complexity: O(n)

 

JavaScript

const MajorityChecker = function (arr) {
  const n = arr.length;

  this.arr = arr;
  this.majorityMap = new Map();
  this.checkTimes = Math.ceil(Math.log2(10 ** 4));

  for (let index = 0; index < n; index++) {
    const num = arr[index];

    if (!this.majorityMap.has(num)) {
      this.majorityMap.set(num, []);
    }
    const indices = this.majorityMap.get(num);

    indices.push(index);
  }
};

MajorityChecker.prototype.query = function (left, right, threshold) {
  const findIndex = (indices, target) => {
    let low = 0;
    let high = indices.length - 1;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);

      indices[mid] > target ? (high = mid - 1) : (low = mid + 1);
    }
    return { low, high };
  };

  for (let index = 0; index < this.checkTimes; index++) {
    const random = Math.floor(Math.random() * (right - left) + left);
    const num = this.arr[random];
    const indices = this.majorityMap.get(num);
    const { low: leftIndex } = findIndex(indices, left - 1);
    const { high: rightIndex } = findIndex(indices, right);

    if (rightIndex < leftIndex) continue;
    if (rightIndex - leftIndex + 1 >= threshold) return num;
  }
  return -1;
};