{x}
blog image

Range Frequency Queries

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

 

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

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i], value <= 104
  • 0 <= left <= right < arr.length
  • At most 105 calls will be made to query

Solution Explanation: Range Frequency Queries

This problem asks to design a data structure that efficiently handles frequency queries on subarrays. The optimal solution leverages a combination of hashing and binary search for efficient lookups.

The core idea is to pre-process the input array arr to create a data structure that allows for quick frequency counting within specified ranges. We achieve this using a hash table (or dictionary in Python) where:

  • Keys: Represent the unique values in arr.
  • Values: Are lists (or arrays) containing the indices where each key (value) appears in arr.

Constructor (__init__ or constructor)

The constructor iterates through arr. For each element, it adds the element's value as a key to the hash table. If the key already exists, the current index is appended to its associated index list; otherwise, a new entry is created with a list containing the current index.

Query Function (query)

The query function takes left, right, and value as input. It performs the following steps:

  1. Check for Existence: It first checks if value exists as a key in the hash table. If not, the frequency is 0, and the function returns 0.

  2. Binary Search: If value exists, it retrieves the associated index list (idx). Crucially, we use binary search (via bisect_left in Python or Collections.binarySearch in Java, lower_bound in C++, sort.SearchInts in Go, and a custom binary search in TypeScript) to find:

    • l: The index of the first element in idx that is greater than or equal to left.
    • r: The index of the first element in idx that is greater than right.

  3. Frequency Calculation: The difference r - l represents the number of indices within the range [left, right] where value appears. This is the frequency, which is returned.

Time and Space Complexity Analysis

  • Time Complexity:

    • Constructor: O(N log N) where N is the length of arr. This is due to the initial iteration through the array (O(N)) plus potentially sorting the index lists (though in practice, many hash table implementations don't explicitly sort lists).
    • Query: O(log N) for each query because of the binary search on the (potentially sorted) index lists.

  • Space Complexity: O(N) in the worst case to store the hash table. The total size of all index lists will be at most N.

Code Examples (Multiple Languages)

The code examples provided in the original response are accurate and demonstrate the described approach in several programming languages. The comments within the code further clarify the implementation details. The key aspects are the use of a hash table for efficient value lookups and binary search for efficient range queries within the index lists.