# Range Frequency Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/range-frequency-queries)
Canonical: https://scaleengineer.com/dsa/problems/range-frequency-queries
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table, Segment Tree
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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. `arr[left...right]` denotes the subarray that contains the elements of `nums` between indices `left` and `right` (**inclusive**).

**Example 1:**

**Input**
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
**Output**
[null, 1, 2]

**Explanation**
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

**Constraints:**

* `1 <= arr.length <= 105`
* `1 <= arr[i], value <= 104`
* `0 <= left <= right < arr.length`
* At most `105` calls will be made to `query`

# Approaches
## Brute Force Iteration
The most straightforward approach is to simply iterate through the specified subarray for each query. We store the original array and for every call to `query`, we loop from the `left` index to the `right` index, counting how many times the `value` appears.
**Time:** Constructor: O(N) to create a copy of the array.
Query: O(right - left + 1), which is O(N) in the worst case, where N is the length of the array. For Q queries, the total time complexity would be O(Q * N). · **Space:** O(N) to store a copy of the input array of size N. If we store a reference, it's O(1).
**Pros:** Very simple to understand and implement.; The constructor is very fast, O(1) if storing a reference or O(N) for a copy.; Requires minimal extra space (O(N) for a copy, O(1) for a reference).
**Cons:** The query time is linear with respect to the range size, which can be up to the entire array length.; This approach is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
In this brute-force method, the constructor `RangeFreqQuery(int[] arr)` has a minimal role; it just stores a reference to or a copy of the input array. The main work is done in the `query(int left, int right, int value)` method. This method implements a simple linear scan over the portion of the array from index `left` to `right`. It uses a counter, initialized to zero, which is incremented each time an element equal to `value` is encountered within the range. While this approach is easy to understand and implement, its performance degrades significantly as the size of the query range and the number of queries increase.

```java
class RangeFreqQuery {
    private int[] data;

    public RangeFreqQuery(int[] arr) {
        this.data = arr;
    }

    public int query(int left, int right, int value) {
        int frequency = 0;
        for (int i = left; i <= right; i++) {
            if (this.data[i] == value) {
                frequency++;
            }
        }
        return frequency;
    }
}
```
### Algorithm
- In the constructor, store the input array `arr`.
- In the `query(left, right, value)` method:
  - Initialize a counter `count` to 0.
  - Loop through the array from index `left` to `right`.
  - If the element at the current index `i` is equal to `value`, increment `count`.
  - After the loop finishes, return `count`.

## HashMap of Indices with Binary Search
A much more efficient approach involves pre-processing the array to answer queries faster. We can use a HashMap to store the indices of every unique number in the array. Each key in the map is a number from the array, and its value is a sorted list of indices where that number appears. When a query comes, we can use binary search on the list of indices for the given value to find how many occurrences fall within the `[left, right]` range.
**Time:** Constructor: O(N) to iterate through the array and populate the HashMap.
Query: O(log K), where K is the number of occurrences of the queried value. In the worst case, K can be N, so the query time is O(log N). For Q queries, the total time is O(N + Q * log N). · **Space:** O(N), as the HashMap stores a list of indices for each unique number. The total number of indices stored across all lists is N.
**Pros:** Extremely fast query time of O(log N), making it highly efficient for a large number of queries.; The constructor has a linear time complexity, which is efficient for pre-processing.
**Cons:** Requires additional space to store the HashMap of indices, which can be up to O(N).; Slightly more complex to implement due to the use of a HashMap and binary search.
### Explanation
This optimized approach leverages pre-computation to achieve logarithmic time queries. 

**Constructor:** We build a `HashMap<Integer, List<Integer>>`. We iterate through the input array once. For each element `arr[i]`, we add the index `i` to the list corresponding to the key `arr[i]`. Since we iterate from index 0 to N-1, the list of indices for each number will be inherently sorted in increasing order.

**Query:** To find the frequency of `value` in `arr[left...right]`, we first retrieve the list of its indices from the map. If the value is not in the map, its frequency is zero. Otherwise, we need to count how many indices in the sorted list fall within the `[left, right]` interval. This is a classic binary search problem. We can find the index of the first element `>= left` (let's call it `start`) and the index of the first element `> right` (let's call it `end`). The number of elements in the range is simply `end - start`.

```java
import java.util.*;

class RangeFreqQuery {
    private Map<Integer, List<Integer>> valueToIndicesMap;

    public RangeFreqQuery(int[] arr) {
        valueToIndicesMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            valueToIndicesMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int query(int left, int right, int value) {
        if (!valueToIndicesMap.containsKey(value)) {
            return 0;
        }

        List<Integer> indices = valueToIndicesMap.get(value);
        
        int startIdx = findLowerBound(indices, left);
        int endIdx = findUpperBound(indices, right);
        
        return endIdx - startIdx;
    }

    // Finds the index of the first element >= target
    private int findLowerBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    // Finds the index of the first element > target
    private int findUpperBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
```
### Algorithm
- **Constructor:**
  - Initialize a `HashMap<Integer, List<Integer>>` to map each value to a list of its indices.
  - Iterate through the input array `arr` from left to right.
  - For each element `arr[i]`, add its index `i` to the list associated with the value `arr[i]` in the HashMap. The lists of indices will be naturally sorted.
- **Query:**
  - Look up `value` in the HashMap. If it's not found, return 0.
  - Retrieve the sorted list of indices for `value`.
  - Use binary search to find the number of indices in the list that are within the range `[left, right]`.
  - This can be calculated as `(count of indices <= right) - (count of indices < left)`.
  - These counts can be found efficiently by locating the insertion points for `right` (specifically, `upper_bound`) and `left` (specifically, `lower_bound`) in the indices list.
  - The difference between these two insertion points gives the frequency.

# Solutions
### CSharp

```csharp
public class RangeFreqQuery { private Dictionary < int , List < int >> g ; public RangeFreqQuery ( int [] arr ) { g = new Dictionary < int , List < int >>(); for ( int i = 0 ; i < arr . Length ; ++ i ) { if (! g . ContainsKey ( arr [ i ])) { g [ arr [ i ]] = new List < int >(); } g [ arr [ i ]]. Add ( i ); } } public int Query ( int left , int right , int value ) { if ( g . ContainsKey ( value )) { var idx = g [ value ]; int l = idx . BinarySearch ( left ); int r = idx . BinarySearch ( right + 1 ); l = l < 0 ? - l - 1 : l ; r = r < 0 ? - r - 1 : r ; return r - l ; } return 0 ; } } /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery obj = new RangeFreqQuery(arr); * int param_1 = obj.Query(left, right, value); */
```

### Java

```java
class RangeFreqQuery { private Map < Integer , List < Integer >> mp = new HashMap <>(); public RangeFreqQuery ( int [] arr ) { for ( int i = 0 ; i < arr . length ; ++ i ) { mp . computeIfAbsent ( arr [ i ], k -> new ArrayList <>()). add ( i ); } } public int query ( int left , int right , int value ) { if (! mp . containsKey ( value )) { return 0 ; } List < Integer > arr = mp . get ( value ); int l = search ( arr , left - 1 ); int r = search ( arr , right ); return r - l ; } private int search ( List < Integer > arr , int val ) { int left = 0 , right = arr . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( arr . get ( mid ) > val ) { right = mid ; } else { left = mid + 1 ; } } return left ; } } /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery obj = new RangeFreqQuery(arr); * int param_1 = obj.query(left,right,value); */
```

### JavaScript

```javascript
/** * @param {number[]} arr */ var RangeFreqQuery = function (arr) {
  this.g = new Map();
  for (let i = 0; i < arr.length; ++i) {
    if (!this.g.has(arr[i])) {
      this.g.set(arr[i], []);
    }
    this.g.get(arr[i]).push(i);
  }
};
/** * @param {number} left * @param {number} right * @param {number} value * @return {number} */ RangeFreqQuery.prototype.query =
  function (left, right, value) {
    const idx = this.g.get(value);
    if (!idx) {
      return 0;
    }
    const l = _.sortedIndex(idx, left);
    const r = _.sortedIndex(idx, right + 1);
    return r - l;
  }; /** * Your RangeFreqQuery object will be instantiated and called as such: * var obj = new RangeFreqQuery(arr) * var param_1 = obj.query(left,right,value) */

```

### CPP

```cpp
class RangeFreqQuery { public: unordered_map < int , vector < int >> mp ; RangeFreqQuery ( vector < int >& arr ) { for ( int i = 0 ; i < arr . size (); ++ i ) mp [ arr [ i ]]. push_back ( i ); } int query ( int left , int right , int value ) { if ( ! mp . count ( value )) return 0 ; auto & arr = mp [ value ]; auto l = upper_bound ( arr . begin (), arr . end (), left - 1 ); auto r = upper_bound ( arr . begin (), arr . end (), right ); return r - l ; } }; /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery* obj = new RangeFreqQuery(arr); * int param_1 = obj->query(left,right,value); */
```

### Python

```python
class RangeFreqQuery : def __init__ ( self , arr : List [ int ]): self . mp = defaultdict ( list ) for i , x in enumerate ( arr ): self . mp [ x ]. append ( i ) def query ( self , left : int , right : int , value : int ) -> int : if value not in self . mp : return 0 arr = self . mp [ value ] l , r = bisect_right ( arr , left - 1 ), bisect_right ( arr , right ) return r - l # Your RangeFreqQuery object will be instantiated and called as such: # obj = RangeFreqQuery(arr) # param_1 = obj.query(left,right,value)
```