Design a data structure that can query the frequency of a given value in a given 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] (inclusive).

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:

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 entire array.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^4
  • 0 <= left <= right < arr.length
  • At most 10^5 calls will be made to query.

Thinking Process

  1. Preprocessing is Key: Building index map once allows fast queries
    • lower_bound: First index >= left (inclusive start)
    • upper_bound: First index > right (exclusive end)
    • Difference gives count in range
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class RangeFreqQuery {
public:
    RangeFreqQuery(vector<int>& arr) {
        for(int i = 0; i < (int)arr.size(); i++) {
            freqArray[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        if(!freqArray.contains(value)) return 0;
        vector<int>& v = freqArray[value];
        auto itLeft = lower_bound(v.begin(), v.end(), left);
        auto itRight = upper_bound(v.begin(), v.end(), right);
        return itRight - itLeft;
    }

private:
    unordered_map<int, vector<int>> freqArray;
};

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

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Preprocessing is Key: Building index map once allows fast queries

How the code works:

  1. Preprocessing is Key: Building index map once allows fast queries
    • lower_bound: First index >= left (inclusive start)
    • upper_bound: First index > right (exclusive end)
    • Difference gives count in range
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.

      Common Mistakes

  2. Value not in array: query(0, 5, 99) → return 0
  3. Value not in range: query(3, 5, 33) when 33 only at indices [1, 7] → return 0
  4. Single occurrence: query(0, 11, 4) → return 1
  5. All occurrences: query(0, 11, 33) → return 2

  6. Single element range: query(2, 2, 4) → return 1 if arr[2] == 4

  7. Wrong binary search bounds: Using upper_bound for both ends
  8. Not checking existence: Accessing freqArray[value] without checking
  9. Index confusion: Mixing 0-indexed and 1-indexed arrays
  10. Not using sorted indices: Assuming indices are sorted without verification
  11. Inefficient approach: Linear scan for each query (O(n) per query)

Key Takeaways

  1. Preprocessing is Key: Building index map once allows fast queries
  2. Sorted Indices: Since we iterate in order, indices are naturally sorted
  3. Binary Search: Efficiently find indices in range [left, right]
  4. lower_bound vs upper_bound:
    • lower_bound: First index >= left (inclusive start)
    • upper_bound: First index > right (exclusive end)
    • Difference gives count in range
  5. Hash Map Lookup: O(1) average case to get indices for a value

References

Template Reference