2080. Range Frequency Queries Solution

The problem

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 <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

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.

Approach 1: Brute Force Approach

In this approach, for each query, we will iterate over the subarray to count the occurrences of the given value. Although this approach is straightforward and easy to implement, it is inefficient since each query will take O(n) time in the worst case, where n is the length of the subarray.

Python

class RangeFreqQuery:
    def __init__(self, arr):
        self.arr = arr

    def query(self, left, right, value):
        return sum(1 for i in range(left, right + 1) if self.arr[i] == value)

arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]
rfq = RangeFreqQuery(arr)
print(rfq.query(1, 2, 4))
print(rfq.query(0, 11, 33))

Java

import java.util.*;

class RangeFreqQuery {
    private int[] arr;
    
    public RangeFreqQuery(int[] arr) {
        this.arr = arr;
    }
    
    public int query(int left, int right, int value) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] == value) {
                count++;
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
        RangeFreqQuery rangeFreqQuery = new RangeFreqQuery(arr);
        System.out.println(rangeFreqQuery.query(1, 2, 4));
        System.out.println(rangeFreqQuery.query(0, 11, 33));
    }
}

C++

#include <iostream>
#include <vector>

class RangeFreqQuery {
public:
    RangeFreqQuery(std::vector<int>& arr) : arr(arr) {}

    int query(int left, int right, int value) {
        int count = 0;
        for (int i = left; i <= right; ++i) {
            if (arr[i] == value) {
                ++count;
            }
        }
        return count;
    }

private:
    std::vector<int> arr;
};

int main() {
    std::vector<int> arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
    RangeFreqQuery rfq(arr);
    std::cout << rfq.query(1, 2, 4) << std::endl;
    std::cout << rfq.query(0, 11, 33) << std::endl;
    return 0;
}

JavaScript

class RangeFreqQuery {
  constructor(arr) {
    this.arr = arr;
  }

  query(left, right, value) {
    let count = 0;
    for (let i = left; i <= right; i++) {
      if (this.arr[i] === value) {
        count++;
      }
    }
    return count;
  }
}

const arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56];
const rfq = new RangeFreqQuery(arr);
console.log(rfq.query(1, 2, 4));
console.log(rfq.query(0, 11, 33));

#include <stdio.h>

int countFrequency(int arr[], int left, int right, int value) {
    int count = 0;
    for (int i = left; i <= right; i++) {
        if (arr[i] == value) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
    int left = 1, right = 2, value = 4;
    printf("%d\n", countFrequency(arr, left, right, value));
    left = 0, right = 11, value = 33;
    printf("%d\n", countFrequency(arr, left, right, value));
    return 0;
}

using System;

public class RangeFreqQuery {
    private int[] arr;

    public RangeFreqQuery(int[] arr) {
        this.arr = arr;
    }

    public int Query(int left, int right, int value) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] == value) {
                count++;
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        int[] arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
        RangeFreqQuery rfq = new RangeFreqQuery(arr);
        Console.WriteLine(rfq.Query(1, 2, 4));
        Console.WriteLine(rfq.Query(0, 11, 33));
    }
}

The Python solution uses a generator expression within sum to count occurrences of the value in the subarray.

Complexity

Time Complexity: O(n) per query.
Space Complexity: O(1) since we do not allocate additional data structures.

Try this approach in the editor

Approach 2: Hash Map Preprocessing

In this approach, the array is preprocessed using a hash map, where each value maps to a list of its indices in the array. During a query, we can efficiently count the frequencies using binary search on the stored indices, making the query process much faster.

Python

from collections import defaultdict
import bisect

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

    def query(self, left, right, value):
        indices = self.freq_map.get(value, [])
        left_idx = bisect.bisect_left(indices, left)
        right_idx = bisect.bisect_right(indices, right)
        return right_idx - left_idx

arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]
rfq = RangeFreqQuery(arr)
print(rfq.query(1, 2, 4))
print(rfq.query(0, 11, 33))

Java

import java.util.*;

class RangeFreqQuery {
    private Map<Integer, List<Integer>> map = new HashMap<>();
    
    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], x -> new ArrayList<>()).add(i);
        }
    }
    
    public int query(int left, int right, int value) {
        List<Integer> indices = map.getOrDefault(value, Collections.emptyList());
        int leftIdx = Collections.binarySearch(indices, left);
        int rightIdx = Collections.binarySearch(indices, right);

        if (leftIdx < 0) leftIdx = -leftIdx - 1;
        if (rightIdx < 0) rightIdx = -rightIdx - 2;

        return rightIdx - leftIdx + 1;
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
        RangeFreqQuery rfq = new RangeFreqQuery(arr);
        System.out.println(rfq.query(1, 2, 4));
        System.out.println(rfq.query(0, 11, 33));
    }
}

C++

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

using namespace std;

class RangeFreqQuery {
public:
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) {
            indices_map[arr[i]].push_back(i);
        }
    }

    int query(int left, int right, int value) {
        if (indices_map.find(value) == indices_map.end()) return 0;
        auto& indices = indices_map[value];
        auto left_itr = lower_bound(indices.begin(), indices.end(), left);
        auto right_itr = upper_bound(indices.begin(), indices.end(), right);
        return distance(left_itr, right_itr);
    }

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

int main() {
    vector<int> arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
    RangeFreqQuery rfq(arr);
    cout << rfq.query(1, 2, 4) << endl;
    cout << rfq.query(0, 11, 33) << endl;
    return 0;
}

JavaScript

class RangeFreqQuery {
    constructor(arr) {
        this.map = {};
        arr.forEach((value, index) => {
            if (!this.map[value]) {
                this.map[value] = [];
            }
            this.map[value].push(index);
        });
    }

    query(left, right, value) {
        if (!this.map[value]) return 0;
        const indices = this.map[value];
        const leftIndex = this._binarySearch(indices, left, true);
        const rightIndex = this._binarySearch(indices, right, false);
        return rightIndex - leftIndex + 1;
    }

    _binarySearch(array, target, findFirst) {
        let left = 0, right = array.length - 1, result = -1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (array[mid] === target) {
                result = mid;
                if (findFirst) right = mid - 1;
                else left = mid + 1;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return findFirst ? left : right;
    }
}

const arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56];
const rfq = new RangeFreqQuery(arr);
console.log(rfq.query(1, 2, 4));
console.log(rfq.query(0, 11, 33));

// Complex data structure implementation in C might require significant code. Using pseudocode to represent.
// Assume that a suitable hashmap or dictionary is implemented as part of this code.

#include <stdio.h>
#include <stdlib.h>

// Assume HashMap and utility methods are implemented.

int* countArray;

void preprocess(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        // Process to store index for each value in arr
        // Use existing or create entry in hashmap for arr[i]
    }
}

int query(int left, int right, int value) {
    // Use hashmap to get list of indices for value,
    // then use binary search to find count in range.
    return 0; // Placeholder, actual return should be the count.
}

int main() {
    int arr[] = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
    // Sample use of preprocessing and querying.
}

using System;
using System.Collections.Generic;

public class RangeFreqQuery {
    private Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            if (!map.ContainsKey(arr[i])) {
                map[arr[i]] = new List<int>();
            }
            map[arr[i]].Add(i);
        }
    }

    public int Query(int left, int right, int value) {
        if (!map.ContainsKey(value)) return 0;
        var indices = map[value];
        int leftBound = indices.BinarySearch(left);
        int rightBound = indices.BinarySearch(right);

        if (leftBound < 0) leftBound = ~leftBound;
        if (rightBound < 0) rightBound = ~rightBound - 1;
        else rightBound++;

        return rightBound - leftBound;
    }

    public static void Main(string[] args) {
        int[] arr = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
        RangeFreqQuery rfq = new RangeFreqQuery(arr);
        Console.WriteLine(rfq.Query(1, 2, 4));
        Console.WriteLine(rfq.Query(0, 11, 33));
    }
}

This Python-based solution uses defaultdict from collections to store lists of indices. The bisect_left and bisect_right functions effectively find the boundary for counting values within a specific range of indices.

Complexity

Time Complexity: Preprocessing takes O(n), while queries use O(log k) where k is the number of appearances of the value.
Space Complexity: O(n) due to storing indices' lists for each element.

Try this approach in the editor

Approach 3: Hash Table + Binary Search

We use a hash table g to store the array of indices corresponding to each value. In the constructor, we traverse the array arr, adding the index corresponding to each value to the hash table.

In the query function, we first check whether the given value exists in the hash table. If it does not exist, it means that the value does not exist in the array, so we directly return 0. Otherwise, we get the index array idx corresponding to the value. Then we use binary search to find the first index l that is greater than or equal to left, and the first index r that is greater than right. Finally, we return r - l.

In terms of time complexity, the time complexity of the constructor is O(n), and the time complexity of the query function is O(log n). The space complexity is O(n). Where n is the length of the array.

TypeScript

class RangeFreqQuery {
    private g: Map<number, number[]> = new Map();

    constructor(arr: number[]) {
        for (let i = 0; i < arr.length; ++i) {
            if (!this.g.has(arr[i])) {
                this.g.set(arr[i], []);
            }
            this.g.get(arr[i])!.push(i);
        }
    }

    query(left: number, right: number, value: number): number {
        const idx = this.g.get(value);
        if (!idx) {
            return 0;
        }
        const l = _.sortedIndex(idx, left);
        const r = _.sortedIndex(idx, right + 1);
        return r - l;
    }
}

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

type RangeFreqQuery struct {
	g map[int][]int
}

func Constructor(arr []int) RangeFreqQuery {
	g := make(map[int][]int)
	for i, v := range arr {
		g[v] = append(g[v], i)
	}
	return RangeFreqQuery{g}
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
	if idx, ok := this.g[value]; ok {
		l := sort.SearchInts(idx, left)
		r := sort.SearchInts(idx, right+1)
		return r - l
	}
	return 0
}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,value);
 */

Rust

use std::collections::HashMap;

struct RangeFreqQuery {
    g: HashMap<i32, Vec<usize>>,
}

impl RangeFreqQuery {
    fn new(arr: Vec<i32>) -> Self {
        let mut g = HashMap::new();
        for (i, &value) in arr.iter().enumerate() {
            g.entry(value).or_insert_with(Vec::new).push(i);
        }
        RangeFreqQuery { g }
    }

    fn query(&self, left: i32, right: i32, value: i32) -> i32 {
        if let Some(idx) = self.g.get(&value) {
            let l = idx.partition_point(|&x| x < left as usize);
            let r = idx.partition_point(|&x| x <= right as usize);
            return (r - l) as i32;
        }
        0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n) per query. Space Complexity: O(1) since we do not allocate additional data structures.
Hash Map Preprocessing	Time Complexity: Preprocessing takes O(n), while queries use O(log k) where k is the number of appearances of the value. Space Complexity: O(n) due to storing indices' lists for each element.
Hash Table + Binary Search	–

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

Frequently asked questions

Is Range Frequency Queries easy or hard?

Range Frequency Queries is considered a Medium difficulty problem. The brute force idea is straightforward, but the intended solution requires recognizing that storing indices and applying binary search enables efficient repeated queries.

Range Frequency Queries Python/Java solution

In Python, use a dictionary mapping values to lists of indices and the bisect module for binary search. In Java, use a HashMap<Integer, List<Integer>> and Collections.binarySearch or custom lower/upper bound logic. Both implementations achieve O(n) preprocessing and O(log k) per query.

How to solve Range Frequency Queries in O(n)?

Build a map from each value to a sorted list of its indices by scanning the array once. This preprocessing step takes O(n). Each query then uses two binary searches on that list to count how many indices fall between left and right, giving O(log k) query time.

What is the best approach for Range Frequency Queries?

The most efficient solution preprocesses the array using a hash map that stores the indices of each value. For a query (left, right, value), retrieve the index list for that value and run two binary searches to find how many indices fall inside the range. Preprocessing takes O(n) time and each query runs in O(log k), where k is the number of occurrences of that value.

Is Range Frequency Queries asked at Google/Amazon/Meta?

Range frequency style problems appear in interviews at large tech companies because they test data structure design and query optimization. Variations involving index preprocessing, binary search, or segment trees are commonly discussed in Google, Amazon, and Meta interview prep.

What data structure is used in Range Frequency Queries?

The typical solution uses a hash map that maps each value to a sorted list of indices where it appears. Binary search is then used on those lists to count elements within a given index range efficiently.

What is the time complexity of Range Frequency Queries?

The optimal implementation runs in O(n) preprocessing time and O(log k) per query using binary search on the stored index list for each value. Space complexity is O(n) because every index from the array is stored in the hash map.

Range Frequency Queries solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Hash Map Preprocessing

Approach 3: Hash Table + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Range Frequency Queries solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Hash Map Preprocessing

Approach 3: Hash Table + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems