2080. Range Frequency Queries

Problem Description

This problem involves creating a data structure that can efficiently find the frequency, or the number of occurrences, of a particular value within a given subarray of an integer array. A subarray is a sequence of contiguous elements from the array, and the frequency of a value is how often it appears within that sequence.

To solve this, one must implement a class RangeFreqQuery with two functionalities:

1. A constructor that takes an integer array arr and prepares it for subsequent queries.
2. A query method that, given a left and right index (left and right) and a value (value), returns how many times value appears between arr[left] and arr[right], inclusive.

Since the array is not modified after the data structure is created, the problem statements suggest preprocessing the array to allow for fast frequency queries.

Intuition

The solution strategy is based on preprocessing the given array to make querying efficient. We make use of the fact that the array remains static after the data structure is constructed. Here's how the solution works:

1. Preprocessing: Instead of checking the frequency of a value each time the query is called, we build a hashmap (or dictionary in Python) upon the class initialization. This hashmap maps each unique value in the array to a list of indices where this value occurs. Because each value is appended in the order of appearance, each list of indices is sorted.

2. Answering Queries: To find the frequency of a value in a particular range, we use binary search to quickly find the position of the left and right boundaries within the preprocessed list of indices for that value. Specifically, we find:

   • The first index in the list that is greater than or equal to left. If left is not in the list, we find the smallest index that is greater than left.
   • The last index in the list that is less than or equal to right. If right is not in the list, we find the largest index that is less than or equal to right.

   The Python module bisect provides the bisect_right function, which can be used to find these indices.

3. Calculating Frequency: The frequency is then the difference between the positions found in the list for right and left. Since bisect_right returns a position one past the last occurrence when searching for right, subtracting these two positions directly gives the correct frequency.

So, the intuition lies in transforming the problem from repetitive frequency counting into a single preprocessing step followed by fast binary search queries.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The implementation of the RangeFreqQuery class involves two core components:

Initialization __init__(self, arr: List[int])

When an object of RangeFreqQuery is created, the constructor takes an input array arr and preprocesses it. The constructor uses a hashmap (self.mp) to store the frequencies. It iterates over the array using enumerate to access both the index i and the value x at that index. Then, it appends the index i to the list corresponding to the value x in the hashmap. This creates a mapping of each unique value to a sorted list of indices where it appears in arr.

Here's a breakdown of the initialization steps:

1self.mp = defaultdict(list)
2for i, x in enumerate(arr):
3    self.mp[x].append(i)

Querying query(self, left: int, right: int, value: int) -> int

The query method is where we find out the frequency of value between the left and right index in the array. We perform two binary searches using bisect_right from the bisect module:

1. Search for the insertion point for left - 1 in the sorted list of indices for value. This gives us l, the number of occurrences of value before the left index.
2. Search for the insertion point for right in the same sorted list. This gives us r, the number of occurrences of value up to and including the right index.

The frequency is then the difference r - l, which is the count of value in the subarray starting at left and ending at right.

The following is the code for the query method:

1if value not in self.mp:
2    return 0
3arr = self.mp[value]
4l, r = bisect_right(arr, left - 1), bisect_right(arr, right)
5return r - l

Notice that we return 0 when the value is not found in self.mp, as it indicates the value does not appear in the array. Otherwise, we calculate the frequency using the binary search results and return it.

In summary, the solution involves a combination of hashmap for preprocessing and binary search for efficient queries. By using these algorithms and data structures, the RangeFreqQuery class allows us to quickly compute the frequency of a value over different subarrays following a single preprocessing pass.

Example Walkthrough

Let's say we have the following array arr = [1, 1, 2, 3, 2, 2, 4, 1, 2], and we want to find out how often particular values appear within specified subarrays of arr.

We initialize the RangeFreqQuery object with arr.

• During the initialization, the object creates a hashmap that will look like this:

  1{
  2  1: [0, 1, 7],
  3  2: [2, 4, 5, 8],
  4  3: [3],
  5  4: [6]
  6}

  Each unique value from arr is now mapped to a sorted list of indices where it appears.

Now, let's suppose we want to find out how often the value 2 appears between indices 2 and 6 (left = 2, right = 6). We perform the following steps:

1. Call the query method with left = 2, right = 6, and value = 2.
2. Look for the sorted list of indices for the value 2 in our hashmap, which is [2, 4, 5, 8].
3. Using the bisect_right function from the bisect module, we find the insertion point for left - 1, which is 1 in this case.
   • bisect_right([2, 4, 5, 8], 1) will return 0 because 1 would fit at the start of the list.
   • This means there are 0 occurrences of 2 before the index '2'.
4. Next, we do a similar search for right, which is 6.
   • bisect_right([2, 4, 5, 8], 6) will return 3 since 6 would fit between 5 and 8.
   • There are 3 occurrences of 2 up to and including index 6.
5. The frequency of value 2 between indices 2 and 6 is therefore 3 - 0 = 3.

Putting it all together, if we wanted to illustrate this using the RangeFreqQuery class and the querying process, we would write the following Python code:

1from collections import defaultdict
2from bisect import bisect_right
3
4class RangeFreqQuery:
5    def __init__(self, arr):
6        self.mp = defaultdict(list)
7        for i, x in enumerate(arr):
8            self.mp[x].append(i)
9
10    def query(self, left, right, value):
11        if value not in self.mp:
12            return 0
13        arr = self.mp[value]
14        l, r = bisect_right(arr, left - 1), bisect_right(arr, right)
15        return r - l
16
17# Initialize with the given array
18rangeFreqQuery = RangeFreqQuery([1, 1, 2, 3, 2, 2, 4, 1, 2])
19
20# Example query
21print(rangeFreqQuery.query(2, 6, 2))  # Output: 3

In this example, the print statement would output 3, as the value 2 occurs three times in the subarray of arr from indices 2 to 6 (inclusive). This walk-through demonstrates the efficiency and effectiveness of the solution approach.

Solution Implementation

Time and Space Complexity

Time Complexity

__init__ constructor:

• The time complexity for initializing the RangeFreqQuery class is O(n), where n is the length of the input array. This is because the constructor iterates through all n elements to populate the self.mp dictionary, which maps each unique value to a list of its indices in the array.

query method:

• The query method utilizes binary search twice through the bisect_right function to find the range of positions of a particular value between indices left and right. Therefore, the time complexity for each query is O(log k), where k is the number of occurrences of the value being queried (k can be at most n).

Space Complexity

• The self.mp dictionary stores lists of indices for each unique value in the array. In the worst case, the space complexity is O(n), if all values are unique and each value appears only once. This would mean that the self.mp dictionary would have n keys with a single index in each list.

In summary, the time complexity is O(n) for the constructor and O(log k) for each query, and the space complexity is up to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.