#1157 - Online Majority Element In Subarray

Hard • View on LeetCode • View on GitHub

Array Binary Search Design Segment Tree Binary Indexed Tree

Problem 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.

Solution

/**
 * @param {number[]} arr
 */
var MajorityChecker = function(arr) {
  this.positionMap = new Map();
  this.array = arr;
  for (let i = 0; i < arr.length; i++) {
    const positions = this.positionMap.get(arr[i]) || [];
    positions.push(i);
    this.positionMap.set(arr[i], positions);
  }
};

/**
 * @param {number} left
 * @param {number} right
 * @param {number} threshold
 * @return {number}
 */
MajorityChecker.prototype.query = function(left, right, threshold) {
  const maxAttempts = 20;
  const rangeLength = right - left + 1;

  for (let attempt = 0; attempt < maxAttempts; attempt++) {
    const candidate = this.array[left + Math.floor(Math.random() * rangeLength)];
    const positions = this.positionMap.get(candidate);
    const count = countInRange(positions, left, right);

    if (count >= threshold) return candidate;
    if (count + rangeLength - count < threshold) return -1;
  }
  return -1;
};

function countInRange(positions, left, right) {
  const leftIndex = lowerBound(positions, left);
  const rightIndex = upperBound(positions, right);
  return rightIndex - leftIndex;
}

function lowerBound(arr, target) {
  let start = 0;
  let end = arr.length;
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] < target) start = mid + 1;
    else end = mid;
  }
  return start;
}

function upperBound(arr, target) {
  let start = 0;
  let end = arr.length;
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] <= target) start = mid + 1;
    else end = mid;
  }
  return start;
}