Range Frequency Queries - Video Solutions
Range Frequency Queries | LeetCode Weekly contest 268 | Most popular concept in CP
Range Frequency Queries - Video Solution
Watch 10 video solutions for Range Frequency Queries, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by Aditya Rajiv has 2,236 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 arrayarr.int query(int left, int right, int value)Returns the frequency ofvaluein the subarrayarr[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 <= 1051 <= arr[i], value <= 1040 <= left <= right < arr.length- At most
105calls will be made toquery
Approach Overview
Problem Overview: You receive an integer array and must repeatedly answer queries of the form (left, right, value). Each query asks how many times value appears between indices left and right inclusive. The challenge is supporting many queries efficiently without scanning the entire range every time.
Approach 1: Brute Force Scan (O(n) per query, O(1) space)
The simplest method directly scans the subarray from left to right. For each index, compare the element with value and increment a counter if it matches. This requires no preprocessing and no additional memory beyond a counter variable. However, every query may examine up to n elements, leading to O(n) time per query and poor performance when the number of queries is large. This approach mainly demonstrates the baseline before applying better array query techniques.
Approach 2: Hash Map Preprocessing + Binary Search (Preprocess O(n), Query O(log k), Space O(n))
A more efficient strategy preprocesses the array by storing the indices of each value. Build a HashMap<value, List<indices>> where every list contains the sorted positions where that value occurs. During a query, retrieve the list for value and use binary search to find the first index >= left and the first index > right. The difference between these positions gives the frequency inside the range.
The key insight: indices are naturally sorted as you traverse the array once. That allows fast range counting using two binary searches instead of scanning the subarray. If a value appears k times overall, the query cost becomes O(log k). Preprocessing the map takes O(n) time and O(n) memory. This pattern is common in problems combining hash tables with range queries.
Some advanced solutions also use a segment tree or other range-query structures, but they are unnecessary here because the value-index mapping already provides efficient lookups.
Recommended for interviews: The hash map + binary search approach is the expected solution. Interviewers want to see that you avoid repeated scans and instead preprocess positions for fast queries. Mentioning the brute force approach first shows understanding of the baseline, while implementing the indexed map demonstrates practical optimization skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n) per query | O(1) | Small arrays or very few queries where preprocessing is unnecessary |
| Hash Map + Binary Search | Preprocess O(n), Query O(log k) | O(n) | Best general solution when many queries must be answered efficiently |