Online majority element in subarray

Array Binary Search Design Binary Indexed Tree Segment Tree

40.1% acceptance

Feb 22, 2026

661

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

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

pub struct MajorityChecker {
  arr: Vec<i32>,
  positions: HashMap<i32, Vec<i32>>, // value -> sorted list of indices
}

impl MajorityChecker {
  pub fn new(arr: Vec<i32>) -> Self {
    let mut positions: HashMap<i32, Vec<i32>> = HashMap::new();
    for (i, &v) in arr.iter().enumerate() {
      positions.entry(v).or_default().push(i as i32);
    }
    MajorityChecker { arr, positions }
  }

  pub fn query(&self, left: i32, right: i32, threshold: i32) -> i32 {
    // Boyer-Moore voting to find candidate
    let (l, r) = (left as usize, right as usize);
    let mut candidate = self.arr[l];
    let mut count = 0;
    for &v in &self.arr[l..=r] {
      if count == 0 { candidate = v; count = 1; }
      else if v == candidate { count += 1; }
      else { count -= 1; }
    }
    // Verify with binary search
    if let Some(pos) = self.positions.get(&candidate) {
      let lo = pos.partition_point(|&x| x < left);
      let hi = pos.partition_point(|&x| x <= right);
      if (hi - lo) as i32 >= threshold { candidate } else { -1 }
    } else {
      -1
    }
  }
}