Threshold majority queries

Array Hash Table Binary Search Divide and Conquer Counting Prefix Sum

21.8% acceptance

Feb 25, 2026

You are given an integer array nums of length n and an array queries, where queries[i] = [li, ri, thresholdi]. Return an array of integers ans where ans[i] is equal to the element in the subarray nums[li...ri] that appears at least thresholdi times, selecting the element with the highest frequency (choosing the smallest in case of a tie), or -1 if no such element exists.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn subarray_majority(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    use std::collections::{BTreeSet, HashMap};

    let n = nums.len();
    let qn = queries.len();
    if qn == 0 {
      return vec![];
    }

    // Mo's algorithm block size: sqrt(n / sqrt(qn)) approximation from C++
    let block_size = ((n as f64 / (qn as f64).sqrt()) as usize).max(1);

    // (l, r, threshold, original_index)
    let mut query_vec: Vec<(usize, usize, usize, usize)> = queries
      .iter()
      .enumerate()
      .map(|(i, q)| (q[0] as usize, q[1] as usize, q[2] as usize, i))
      .collect();

    // Mo's sort: by block, then alternating r direction per block (odd=desc, even=asc)
    query_vec.sort_unstable_by(|a, b| {
      let ba = a.0 / block_size;
      let bb = b.0 / block_size;
      if ba != bb {
        return ba.cmp(&bb);
      }
      if ba & 1 == 1 { b.1.cmp(&a.1) } else { a.1.cmp(&b.1) }
    });

    // freq_map[v]   = current count of v in the window
    // freqs[f]      = BTreeSet of values whose current count equals f
    // max_freq      = highest count currently in the window
    let mut freq_map: HashMap<i32, usize> = HashMap::new();
    let mut freqs: Vec<BTreeSet<i32>> = vec![BTreeSet::new(); n + 1];
    let mut max_freq: usize = 0;

    // Inline helpers via macros (closures can't mutably borrow multiple fields at once)
    macro_rules! add {
      ($idx:expr) => {{
        let num = nums[$idx];
        let old_f = *freq_map.get(&num).unwrap_or(&0);
        if old_f > 0 {
          freqs[old_f].remove(&num);
        }
        let new_f = old_f + 1;
        freq_map.insert(num, new_f);
        freqs[new_f].insert(num);
        if new_f > max_freq {
          max_freq = new_f;
        }
      }};
    }

    macro_rules! remove {
      ($idx:expr) => {{
        let num = nums[$idx];
        let old_f = *freq_map.get(&num).unwrap_or(&0);
        freqs[old_f].remove(&num);
        if old_f > 1 {
          let new_f = old_f - 1;
          freq_map.insert(num, new_f);
          freqs[new_f].insert(num);
        } else {
          freq_map.remove(&num);
        }
        if max_freq > 0 && freqs[max_freq].is_empty() {
          max_freq -= 1;
        }
      }};
    }

    let mut res = vec![-1i32; qn];
    let mut cur_l = 0i64;
    let mut cur_r = -1i64; // empty window

    for (ql, qr, thresh, qi) in &query_vec {
      let (ql, qr) = (*ql as i64, *qr as i64);

      while cur_r < qr { cur_r += 1; add!(cur_r as usize); }
      while cur_l > ql { cur_l -= 1; add!(cur_l as usize); }
      while cur_r > qr { remove!(cur_r as usize); cur_r -= 1; }
      while cur_l < ql { remove!(cur_l as usize); cur_l += 1; }

      if max_freq >= *thresh {
        // Highest-frequency element; BTreeSet gives smallest val on tie
        res[*qi] = *freqs[max_freq].iter().next().unwrap();
      }
    }

    res
  }
}