Skip to content

2080. Range Frequency Queries 👍

  • Time: Constructor: $O(n)$, query(left: int, right: int, value: int): $O(\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class RangeFreqQuery:
  def __init__(self, arr: List[int]):
    self.valueToIndices = collections.defaultdict(list)
    for i, a in enumerate(arr):
      self.valueToIndices[a].append(i)

  def query(self, left: int, right: int, value: int) -> int:
    indices = self.valueToIndices[value]
    i = bisect_left(indices, left)
    j = bisect_right(indices, right)
    return j - i