Range Frequency Queries

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).

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


**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.

Solution

Method 1 - Using Map of List

To solve this problem, we can use a HashMap to preprocess and store the indices of all occurrences of each number in the array. This will allow us to efficiently query the frequency of a value in a given subarray using binary search.

Here are key points:

Data Structure:
- Use a HashMap<Integer, List<Integer>> (or defaultdict in Python) to map each value in the array to its list of indices.
- For example, for the array [1, 2, 1, 3, 1], the map would look like: {1: [0, 2, 4], 2: [1], 3: [3]}.
Preprocessing:
- Iterate through the array, and populate the map such that for each number, we store its list of indices.
- This step takes O(n) time, where n is the size of the array.
Query Operation:
- To determine the number of occurrences of a value in arr[left...right], use the precomputed indices from the HashMap.
- Use binary search (via Collections.binarySearch in Java or bisect in Python) to find:
  - The smallest index in the list that is >= left.
  - The largest index in the list that is <= right.
- The difference between these indices gives the frequency of the value in the subarray.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class RangeFreqQuery {

    private Map<Integer, List<Integer>> indexMap;

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

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

        List<Integer> indices = indexMap.get(value);
        int start = Collections.binarySearch(indices, left);
        int end = Collections.binarySearch(indices, right);

        // Adjust positions to account for binarySearch contract
        if (start < 0) start = -start - 1;
        if (end < 0) end = -end - 2;

        return end - start + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class RangeFreqQuery:
    def __init__(self, arr: List[int]) -> None:
        self.idx_map: Dict[int, List[int]] = {}
        for i, val in enumerate(arr):
            if val not in self.idx_map:
                self.idx_map[val] = []
            self.idx_map[val].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.idx_map:
            return 0
        
        indices = self.idx_map[value]
        start = bisect_left(indices, left)
        end = bisect_right(indices, right) - 1

        return max(0, end - start + 1)

Complexity

⏰ Time complexity
- Preprocessing: O(n)
- Query:
  - Binary searches (O(log k) each) to locate the range of indices, where k is the total number of occurrences of the value in the array.
  - Hence, query complexity is O(log k).
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 - Using Map of List#

Code#

Complexity#