Range Frequency Queries - Practice Coding Problems

Range Frequency Queries - Problem

Array Hash Table Binary Search Design Segment Tree Medium

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 arr between indices left and right (inclusive).

Input & Output

Example 1 — Basic Range Query

$ Input: arr = [1,2,2,3,1], operations = [[0,4,1],[1,3,2]]

› Output: [2,2]

💡 Note: For query [0,4,1]: value 1 appears at indices 0 and 4, both in range → count = 2. For query [1,3,2]: value 2 appears at indices 1 and 2, both in range → count = 2.

Example 2 — Value Not in Range

$ Input: arr = [1,1,1,1], operations = [[1,2,2]]

› Output: [0]

💡 Note: Query [1,2,2]: looking for value 2 in range [1,2], but value 2 doesn't exist in the array → count = 0.

Example 3 — Single Element Range

$ Input: arr = [5,3,5,1,5], operations = [[0,0,5],[2,2,5]]

› Output: [1,1]

💡 Note: Query [0,0,5]: range contains only index 0 with value 5 → count = 1. Query [2,2,5]: range contains only index 2 with value 5 → count = 1.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ value ≤ 10⁴
0 ≤ left ≤ right < arr.length
At most 10⁵ calls to query

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,2,3,1] and query range [1,3] for value 2

Process

Count occurrences of value 2 in positions 1, 2, 3

Output

Return frequency count: 2

Key Takeaway

🎯 Key Insight: Pre-organize indices by value to enable fast range counting with binary search

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to preprocess the array by grouping indices by their values in a hash map. For each query, use binary search on the sorted index list to count occurrences within the given range. Best approach uses Hash Map with Binary Search for O(log n) query time after O(n) preprocessing. Time: O(log n) per query, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Index Lists	O(log n)	O(n)	Store indices for each value, then count within range using binary search
Brute Force	O(n)	O(1)	For each query, iterate through the range and count occurrences

Hash Map with Index Lists — Algorithm Steps

Build hash map: value -> list of indices
For each query, get the index list for the target value
Use binary search to count indices within [left, right]

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Index Map

Group all indices by their values

Binary Search Range

Use binary search to find count within [left, right]

Return Count

Calculate rightPos - leftPos

Code -

solution.c — C

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

#define MAX_VAL 1000001
#define MAX_SIZE 100000

typedef struct {
    int* indices[MAX_VAL];
    int sizes[MAX_VAL];
    int capacities[MAX_VAL];
} RangeFreqQuery;

int binarySearch(int* arr, int size, int target, int isUpper) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (isUpper ? arr[mid] <= target : arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

RangeFreqQuery* rangeFreqQueryCreate(int* arr, int arrSize) {
    RangeFreqQuery* obj = (RangeFreqQuery*)calloc(1, sizeof(RangeFreqQuery));
    
    for (int i = 0; i < arrSize; i++) {
        int val = arr[i] + 50000; // Offset for negative values
        if (obj->indices[val] == NULL) {
            obj->capacities[val] = 10;
            obj->indices[val] = (int*)malloc(obj->capacities[val] * sizeof(int));
        }
        if (obj->sizes[val] >= obj->capacities[val]) {
            obj->capacities[val] *= 2;
            obj->indices[val] = (int*)realloc(obj->indices[val], obj->capacities[val] * sizeof(int));
        }
        obj->indices[val][obj->sizes[val]++] = i;
    }
    
    return obj;
}

int rangeFreqQueryQuery(RangeFreqQuery* obj, int left, int right, int value) {
    int val = value + 50000; // Offset for negative values
    if (obj->indices[val] == NULL) return 0;
    
    int leftPos = binarySearch(obj->indices[val], obj->sizes[val], left, 0);
    int rightPos = binarySearch(obj->indices[val], obj->sizes[val], right, 1);
    return rightPos - leftPos;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse operations
    fgets(line, sizeof(line), stdin);
    int operations[100][3];
    int opCount = 0;
    
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[') {
            ptr++;
            operations[opCount][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            operations[opCount][1] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            operations[opCount][2] = atoi(ptr);
            opCount++;
            while (*ptr != ']') ptr++;
        }
        ptr++;
    }
    
    RangeFreqQuery* rfq = rangeFreqQueryCreate(arr, arrSize);
    
    printf("[");
    for (int i = 0; i < opCount; i++) {
        int result = rangeFreqQueryQuery(rfq, operations[i][0], operations[i][1], operations[i][2]);
        printf("%d", result);
        if (i < opCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

After O(n) preprocessing, each query uses binary search on the index list

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores all indices organized by value

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Index Lists — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler