Problem Description

The Range Frequency Queries problem requires designing a data structure that efficiently answers queries about the frequency of a value within a specific subarray range.

You are given an integer array arr. Implement a class that supports two operations:

• RangeFreqQuery(int[] arr): Initializes the object with the array arr.
• int query(int left, int right, int value): Returns the number of occurrences of value in the subarray arr[left...right] (inclusive).

• 1 ≤ arr.length ≤ 105
• 0 ≤ arr[i], value ≤ 104
• There can be up to 105 queries.
• Queries may overlap and are independent.

Thought Process

The first idea might be to use a brute-force approach: for each query, simply iterate from left to right and count how many times value appears. However, this method is inefficient for large arrays or many queries, as each query could take up to O(n) time.

To optimize, we need a way to quickly count the number of times a value appears in any given range. This suggests preprocessing: if we can preprocess the array to store information that allows us to answer queries in logarithmic or constant time, the overall performance will improve significantly.

One intuitive idea is to record the positions (indices) of each unique value in arr. Then, for any query, we can use binary search to count how many of those positions fall within the range [left, right].

Solution Approach

The optimized solution involves two main steps:

1. Preprocessing:
   • For each unique value in arr, store a sorted list of all indices where that value occurs.
   • This can be done in a single pass through the array using a hash map (dictionary) where keys are values from arr and values are lists of indices.
2. Querying:
   • To answer query(left, right, value):
   • Retrieve the list of indices for value.
   • Use binary search to find:
     • The first index in the list that is greater than or equal to left (lower bound).
     • The first index in the list that is greater than right (upper bound).
   • The count is the difference between the upper and lower bounds.

Example Walkthrough

Input: arr = [1, 3, 3, 2, 3, 1, 2]
Suppose we want to answer query(2, 5, 3) ("How many times does 3 appear between indices 2 and 5?").

Step 1: Preprocess

• Map of value to indices:
  • 1: [0, 5]
  • 2: [3, 6]
  • 3: [1, 2, 4]

• Indices for 3: [1, 2, 4]
• Use binary search to find:
  • First index ≥ 2 (which is at position 1 in the list, value 2)
  • First index > 5 (which is beyond the end of the list, so index 3)
• Count = 3 - 1 = 2

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n) per query (where n is the array length).
• Space Complexity: O(1) extra space.

• Preprocessing Time: O(n) (one pass through the array).
• Query Time: O(log k) per query (where k is the number of occurrences of the queried value).
• Space Complexity: O(n) (for the positions map).

Summary

The key to efficiently solving the Range Frequency Queries problem is to preprocess the array by mapping each value to its list of occurrence indices. This allows us to answer each query using binary search, making each query very fast even for large arrays and many queries. The solution is elegant because it leverages preprocessing and binary search to transform a potentially slow operation into a quick one, demonstrating the power of combining data structures and algorithms for optimal performance.

Code Implementation

from bisect import bisect_left, bisect_right
from collections import defaultdict

class RangeFreqQuery:
    def __init__(self, arr):
        self.pos = defaultdict(list)
        for idx, val in enumerate(arr):
            self.pos[val].append(idx)

    def query(self, left, right, value):
        idxs = self.pos.get(value, [])
        l = bisect_left(idxs, left)
        r = bisect_right(idxs, right)
        return r - l
      

#include <vector>
#include <unordered_map>
#include <algorithm>

class RangeFreqQuery {
    std::unordered_map<int, std::vector<int>> pos;
public:
    RangeFreqQuery(std::vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) {
            pos[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        auto it = pos.find(value);
        if (it == pos.end()) return 0;
        const std::vector<int>& idxs = it->second;
        auto l = std::lower_bound(idxs.begin(), idxs.end(), left);
        auto r = std::upper_bound(idxs.begin(), idxs.end(), right);
        return r - l;
    }
};
      

import java.util.*;

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

    public RangeFreqQuery(int[] arr) {
        pos = new HashMap<>();
        for (int i = 0; i < arr.length; ++i) {
            pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }
    
    public int query(int left, int right, int value) {
        List<Integer> idxs = pos.get(value);
        if (idxs == null) return 0;
        int l = Collections.binarySearch(idxs, left);
        int r = Collections.binarySearch(idxs, right + 1);
        if (l < 0) l = -l - 1;
        if (r < 0) r = -r - 1;
        return r - l;
    }
}
      

class RangeFreqQuery {
    constructor(arr) {
        this.pos = new Map();
        for (let i = 0; i < arr.length; i++) {
            if (!this.pos.has(arr[i])) this.pos.set(arr[i], []);
            this.pos.get(arr[i]).push(i);
        }
    }
    
    query(left, right, value) {
        if (!this.pos.has(value)) return 0;
        const idxs = this.pos.get(value);
        const lower = this.lowerBound(idxs, left);
        const upper = this.upperBound(idxs, right);
        return upper - lower;
    }
    
    lowerBound(arr, target) {
        let l = 0, r = arr.length;
        while (l < r) {
            let m = (l + r) >> 1;
            if (arr[m] < target) l = m + 1;
            else r = m;
        }
        return l;
    }
    
    upperBound(arr, target) {
        let l = 0, r = arr.length;
        while (l < r) {
            let m = (l + r) >> 1;
            if (arr[m] <= target) l = m + 1;
            else r = m;
        }
        return l;
    }
}