Problem statement

Answer many questions of the form "how often does value occur in this stretch of the array?" quickly.

Write the class RangeFreqQuery:

• RangeFreqQuery(int[] arr) stores the 0-indexed array arr.
• int query(int left, int right, int value) returns how many times value occurs in the subarray arr[left..right] (both ends included).

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["RangeFreqQuery","query","query","query"]
[[[12,33,4,56,22,2,34,33,22,12,34,56]],[1,2,4],[0,11,33],[4,8,22]]
Output: [null,1,2,2]
Explanation: 4 occurs once in [33,4]. 33 occurs twice in the whole array. In [22,2,34,33,22] the value 22 occurs twice.

Example 2

Input: ["RangeFreqQuery","query","query"]
[[[7,7,7]],[0,0,7],[1,2,5]]
Output: [null,1,0]
Explanation: The single element at index 0 is 7; there is no 5 at all.

Constraints

• 1 <= arr.length <= 10^5
• 1 <= arr[i], value <= 10^4
• 0 <= left <= right < arr.length
• At most 10^5 calls are made to query

Hints for Range Frequency Queries

1. Hint 1

   Counting through the range is O(n) per query — 10^10 steps at the limits. Precompute something per value instead.

2. Hint 2

   For each value, record the sorted list of indices where it occurs (one left-to-right pass builds them all already sorted).

3. Hint 3

   The answer is the number of those indices inside [left, right]: binary search for the first index >= left and the first index > right, and subtract.

How to solve Range Frequency Queries

Group the indices by value. Each group is sorted, so the occurrences inside [left, right] form a contiguous block of it whose size two binary searches give.

Approach

1. Constructor: for i from 0 to n - 1, append i to positions[arr[i]].
2. query(left, right, value): if value has no positions, return 0.
3. Otherwise return upperBound(positions[value], right) - lowerBound(positions[value], left) — the number of stored indices i with left <= i <= right.

Why it works

positions[value] lists exactly the indices holding value, in increasing order because they were appended left to right. In a sorted list, the elements in [left, right] are those from the first one >= left up to (not including) the first one > right, so the difference of the two search positions is their count.

Complexity

• Time — O(n) to build, O(log n) per query
• Space — O(n)

Pitfalls

• The range is inclusive on both ends: search > right for the end, not >= right.
• A value that never occurs has no list; answer 0 instead of indexing a missing key.
• A segment tree of frequency maps also works, but it costs O(n log n) memory for no gain here.

Reference solution

Python

import bisect

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.pos = {}
        for i, v in enumerate(arr):
            self.pos.setdefault(v, []).append(i)  # appended in order, so sorted

    def query(self, left: int, right: int, value: int) -> int:
        p = self.pos.get(value)
        if not p:
            return 0
        return bisect.bisect_right(p, right) - bisect.bisect_left(p, left)

Java

class RangeFreqQuery {
    private HashMap<Integer, List<Integer>> pos = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i); // sorted
    }

    private static int lower(List<Integer> p, int x) { // first index whose position is >= x
        int lo = 0, hi = p.size();
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (p.get(mid) < x) lo = mid + 1; else hi = mid; }
        return lo;
    }

    public int query(int left, int right, int value) {
        List<Integer> p = pos.get(value);
        if (p == null) return 0;
        return lower(p, right + 1) - lower(p, left);
    }
}

C++

class RangeFreqQuery {
    unordered_map<int, vector<int>> pos;
public:
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < (int)arr.size(); i++) pos[arr[i]].push_back(i); // appended in order, so sorted
    }

    int query(int left, int right, int value) {
        auto it = pos.find(value);
        if (it == pos.end()) return 0;
        auto& p = it->second;
        return upper_bound(p.begin(), p.end(), right) - lower_bound(p.begin(), p.end(), left);
    }
};

JavaScript

function rfqLower(p, x) { // first index whose position is >= x
    var lo = 0, hi = p.length;
    while (lo < hi) { var mid = (lo + hi) >> 1; if (p[mid] < x) lo = mid + 1; else hi = mid; }
    return lo;
}

var RangeFreqQuery = function(arr) {
    this.pos = new Map();
    for (var i = 0; i < arr.length; i++) { // appended in order, so sorted
        if (!this.pos.has(arr[i])) this.pos.set(arr[i], []);
        this.pos.get(arr[i]).push(i);
    }
};

RangeFreqQuery.prototype.query = function(left, right, value) {
    var p = this.pos.get(value);
    if (!p) return 0;
    return rfqLower(p, right + 1) - rfqLower(p, left);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Simple Bank System Medium