Scale Engineer

Range Frequency Queries

Med
#1894Time: Constructor: O(N) to create a copy of the array. Query: O(right - left + 1), which is O(N) in the worst case, where N is the length of the array. For Q queries, the total time complexity would be O(Q * N).Space: O(N) to store a copy of the input array of size N. If we store a reference, it's O(1).1 company
Patterns
Design
Algorithms
Binary Search
Data structures
ArrayHash TableSegment Tree
Companies
Quora

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simply iterate through the specified subarray for each query. We store the original array and for every call to query, we loop from the left index to the right index, counting how many times the value appears.

Algorithm

  • In the constructor, store the input array arr.
  • In the query(left, right, value) method:
    • Initialize a counter count to 0.
    • Loop through the array from index left to right.
    • If the element at the current index i is equal to value, increment count.
    • After the loop finishes, return count.

Walkthrough

In this brute-force method, the constructor RangeFreqQuery(int[] arr) has a minimal role; it just stores a reference to or a copy of the input array. The main work is done in the query(int left, int right, int value) method. This method implements a simple linear scan over the portion of the array from index left to right. It uses a counter, initialized to zero, which is incremented each time an element equal to value is encountered within the range. While this approach is easy to understand and implement, its performance degrades significantly as the size of the query range and the number of queries increase.

class RangeFreqQuery {    private int[] data;     public RangeFreqQuery(int[] arr) {        this.data = arr;    }     public int query(int left, int right, int value) {        int frequency = 0;        for (int i = left; i <= right; i++) {            if (this.data[i] == value) {                frequency++;            }        }        return frequency;    }}

Complexity

Time

Constructor: O(N) to create a copy of the array. Query: O(right - left + 1), which is O(N) in the worst case, where N is the length of the array. For Q queries, the total time complexity would be O(Q * N).

Space

O(N) to store a copy of the input array of size N. If we store a reference, it's O(1).

Trade-offs

Pros

  • Very simple to understand and implement.

  • The constructor is very fast, O(1) if storing a reference or O(N) for a copy.

  • Requires minimal extra space (O(N) for a copy, O(1) for a reference).

Cons

  • The query time is linear with respect to the range size, which can be up to the entire array length.

  • This approach is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits.

Solutions

public class RangeFreqQuery { private Dictionary < int , List < int >> g ; public RangeFreqQuery ( int [] arr ) { g = new Dictionary < int , List < int >>(); for ( int i = 0 ; i < arr . Length ; ++ i ) { if (! g . ContainsKey ( arr [ i ])) { g [ arr [ i ]] = new List < int >(); } g [ arr [ i ]]. Add ( i ); } } public int Query ( int left , int right , int value ) { if ( g . ContainsKey ( value )) { var idx = g [ value ]; int l = idx . BinarySearch ( left ); int r = idx . BinarySearch ( right + 1 ); l = l < 0 ? - l - 1 : l ; r = r < 0 ? - r - 1 : r ; return r - l ; } return 0 ; } } /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery obj = new RangeFreqQuery(arr); * int param_1 = obj.Query(left, right, value); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem