Subarray Frequency Count Queries

Intuition

Each query asks how many times a value x appears in an index range [l, r]. If we store all occurrence indices of each value in sorted order, then every query becomes a count of indices within a range, which can be answered quickly using two binary searches.

Algorithm

1Build a map from value to a sorted list of its indices while scanning the array once.
2For each query [l, r, x], fetch x's index list from the map.
3If x does not exist in the map, answer is 0.
4Otherwise, find first index >= l (lower bound) and last index <= r (upper bound).
5Frequency is upper - lower + 1, or 0 if bounds do not overlap.

Example Walkthrough

Input: arr = [1, 2, 1, 3, 1, 2], queries = [[0,5,1],[1,4,2],[2,3,1]]

1.Preprocess positions: 1 -> [0,2,4], 2 -> [1,5], 3 -> [3].
2.Query [0,5,1]: positions in range are [0,2,4] -> 3.
3.Query [1,4,2]: positions in range are [1] -> 1.
4.Query [2,3,1]: positions in range are [2] -> 1.

Output: [3, 1, 1]

Common Pitfalls

•Range endpoints are inclusive; adjust upper-bound math carefully.
•A missing value key must return 0 immediately, not cause null access.
•Per-query linear scans over the whole array will time out for large input sizes.

Subarray Frequency Count Queries.java

Java


import java.util.*;

// Approach: Preprocess positions of each distinct value, then answer each query with binary search on that value's index list.
// Frequency in range [l, r] equals count of stored indices between l and r (inclusive), computed as upperBound(r) - lowerBound(l).
// Time: O(n + q log f) Space: O(n)

class Solution {

    public ArrayList<Integer> freqInRange(int[] arr, int[][] queries) {
        ArrayList<Integer> ans = new ArrayList<>();
        Map<Integer, List<Integer>> mp = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            mp.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
        for (int[] q : queries) {
            List<Integer> idxs = mp.get(q[2]);
            if (idxs == null) {
                ans.add(0);
            } else {
                int lb = Collections.binarySearch(idxs, q[0]);
                if (lb < 0) {
                    lb = -lb - 1;
                }
                int ub = Collections.binarySearch(idxs, q[1]);
                if (ub < 0) {
                    ub = -ub - 2;
                }
                ans.add(ub - lb + 1);
            }
        }
        return ans;
    }
}

Was this solution helpful?