Range frequency queries

Array Hash Table Binary Search Design Segment Tree

42.2% acceptance

Feb 25, 2026

745

Design a data structure to find the frequency of a given value in a given subarray. The frequency of a value in a subarray is the number of occurrences of that value in the subarray. Implement the RangeFreqQuery class: RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr. int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right]. A subarray is a contiguous sequence of elements within an array.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;


pub struct RangeFreqQuery {
  indices: HashMap<i32, Vec<usize>>,
}

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

  pub fn query(&self, left: i32, right: i32, value: i32) -> i32 {
    if let Some(positions) = self.indices.get(&value) {
      let left = left as usize;
      let right = right as usize;
      let lo = positions.partition_point(|&x| x < left);
      let hi = positions.partition_point(|&x| x <= right);
      (hi - lo) as i32
    } else {
      0
    }
  }
}