We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Range Frequency Queries

Number: 1294

Difficulty: Medium

Paid? No

Companies: Quora

Problem Description

Design a data structure that supports counting the frequency of a given integer value within any subarray of a provided array. The data structure must support efficient queries after an initial preprocessing step.

Key Insights

  • Preprocessing is essential since there can be up to 10^5 queries.
  • Use a hash map (or dictionary) to map each distinct value to a sorted list of indices where it appears.
  • Use binary search to quickly count how many indices fall within a given range for a queried value.
  • The approach ensures that each query is processed in logarithmic time relative to the number of occurrences of the value.

Space and Time Complexity

Time Complexity:

  • Preprocessing: O(n), where n is the length of the array.
  • Each query: O(log k), where k is the number of occurrences of the queried value.

Space Complexity:

  • O(n) for storing the indices of each occurrence in the hash map.

Solution

We first build a hash map where the key is the array's value and the corresponding value is a list of sorted indices at which it appears. When a query is performed with a range [left, right] and a target value, we retrieve the sorted list of indices for that value. Using binary search, we can determine:

  1. The first occurrence index in the list that is not less than left.
  2. The first occurrence index in the list that is greater than right. The difference between these two positions gives the count of indices in the range.

The solution leverages sorting, binary search, and hash maps to provide efficient range frequency queries.

Code Solutions

# Python solution using dictionary and bisect for binary search

from bisect import bisect_left, bisect_right

class RangeFreqQuery:
    def __init__(self, arr):
        # Create a dictionary mapping each value to its list of indices where it occurs
        self.value_to_indices = {}
        for index, num in enumerate(arr):
            if num not in self.value_to_indices:
                self.value_to_indices[num] = []
            self.value_to_indices[num].append(index)

    def query(self, left, right, value):
        # If the value is not present in the dictionary, return 0
        if value not in self.value_to_indices:
            return 0
        indices = self.value_to_indices[value]
        # Find leftmost position where index >= left using binary search
        left_pos = bisect_left(indices, left)
        # Find rightmost position where index <= right using binary search
        right_pos = bisect_right(indices, right)
        return right_pos - left_pos

# Example usage:
# arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]
# query = RangeFreqQuery(arr)
# print(query.query(1, 2, 4))   # Expected output: 1
# print(query.query(0, 11, 33))  # Expected output: 2
← Back to All Questions