Leetcode 2080: Range Frequency Queries

Input: The input consists of the following: - `arr`: a 0-indexed integer array. - `query`: a list of queries where each query is represented by three integers: `left`, `right`, and `value`.

Example: [[1, 2, 3, 4, 2, 5, 3, 2], [2, 4, 2], [1, 6, 3]]

Constraints:

• 1 <= arr.length <= 10^5

• 1 <= arr[i], value <= 10^4

• 0 <= left <= right < arr.length

• At most 10^5 calls will be made to query.

Output: For each query, return the frequency of `value` in the subarray `arr[left...right]`.

Example: [null, 2, 2]

Constraints:

• The result for each query should be an integer representing the frequency of `value` in the subarray.

Goal: The goal is to efficiently find the frequency of a specific value in a given subarray.

Steps:

• Create a map to store the indices of each value in the array.

• For each query, use binary search to find the range of indices where the value appears in the subarray.

Goal: The constraints are designed to ensure the data structure can handle large inputs efficiently.

Steps:

• The array can be as large as 10^5 elements.

• Each value in the array can range from 1 to 10^4.

• The number of queries can be up to 10^5.

Assumptions:

• The array is 0-indexed and the queries are based on 0-indexed positions.

• Input: [[1, 2, 3, 4, 2, 5, 3, 2], [2, 4, 2], [1, 6, 3]]

• Explanation: The first query returns `2` because the value `2` appears twice in the subarray [3, 4, 2]. The second query returns `2` because the value `3` appears twice in the subarray [2, 3, 4, 2, 5, 3].

Approach: To solve the problem efficiently, we store the indices of each element in the array. For each query, we perform binary search to find the range of indices where the element occurs, then count the number of occurrences in the given subarray.

Observations:

• Storing indices of each value allows us to quickly look up occurrences within a specific range.

• We need to handle multiple queries efficiently by preprocessing the array.

Steps:

• Preprocess the input array to store indices of each element in a map.

• For each query, use binary search (upper_bound and lower_bound) to find the range of occurrences of the value in the subarray.

Empty Inputs:

• If the array is empty, no queries should be processed.

Large Inputs:

• Handle large arrays efficiently by using binary search for each query.

Special Values:

• If the value does not appear in the subarray, return 0.

Constraints:

• Ensure the solution can handle up to 10^5 queries efficiently.

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) {
    return upper_bound(mp[value].begin(), mp[value].end(), right) -             
        lower_bound(mp[value].begin(), mp[value].end(), left);
}
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);

1 : Variable Declaration

map<int, vector<int>> mp;

This line declares a map `mp` where each key is an integer and its value is a vector of integers, used to store the indices of occurrences of each number in the input array.

2 : Constructor Definition

RangeFreqQuery(vector<int>& arr) {

This is the constructor for the `RangeFreqQuery` class, which initializes the map `mp` by iterating over the input array `arr`.

3 : For Loop

    for(int i = 0; i < arr.size(); i++) {

This `for` loop iterates through the input array `arr` to populate the map `mp` with the indices of each element in the array.

4 : Map Update

        mp[arr[i]].push_back(i);

This line adds the current index `i` to the vector corresponding to the element `arr[i]` in the map `mp`. This helps track the positions where each value occurs in the array.

5 : Method Definition

int query(int left, int right, int value) {

This is the definition of the `query` method, which takes a range `[left, right]` and a target `value`, and returns the frequency of `value` within the specified range.

6 : Range Query Logic

    return upper_bound(mp[value].begin(), mp[value].end(), right) -

This line uses `upper_bound` to find the first index greater than `right` for the target `value` in the map. It calculates the number of occurrences of `value` up to `right`.

7 : Range Query Logic

        lower_bound(mp[value].begin(), mp[value].end(), left);

This line uses `lower_bound` to find the first index greater than or equal to `left`. The difference between the results of `upper_bound` and `lower_bound` gives the number of occurrences of `value` within the range `[left, right]`.

Best Case: O(1) if the value does not appear in the array.

Average Case: O(log n) per query due to binary search.

Worst Case: O(log n) per query, where n is the number of occurrences of the value.

Description: The time complexity is dominated by the binary search operations on the indices.

Best Case: O(n) if all values are unique and stored separately.

Worst Case: O(n) for storing the indices of each value in the map.

Description: Space complexity depends on the size of the input array and the number of distinct values.

Leetcode 2080: Range Frequency Queries

Explore →