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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Range Frequency Queries

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subarray is defined as a contiguous sequence of elements within an array.
  • Efficiently querying the frequency of a number over ranges requires a good data structure.
  • The problem allows for multiple queries, necessitating an optimized approach to avoid repeated scanning of the array.

Space and Time Complexity

Time Complexity: O(1) for constructing the data structure and O(log N) for each query using binary search or O(N) for a direct approach, depending on the implementation. Space Complexity: O(N) for storing the indices of occurrences.

Solution

The solution involves creating a data structure that stores the indices of each unique value in the array. This can be accomplished using a hash map (or dictionary) where the key is the value and the value is a list of indices where that value occurs. When a query is made, we can use binary search to quickly find the range of indices that fall within the specified subarray, allowing us to count the occurrences efficiently.

Code Solutions

class RangeFreqQuery:
    def __init__(self, arr):
        self.indices = {}
        for i, num in enumerate(arr):
            if num not in self.indices:
                self.indices[num] = []
            self.indices[num].append(i)

    def query(self, left, right, value):
        if value not in self.indices:
            return 0
        indices_list = self.indices[value]
        left_index = self._find_left_bound(indices_list, left)
        right_index = self._find_right_bound(indices_list, right)
        return right_index - left_index

    def _find_left_bound(self, indices_list, left):
        low, high = 0, len(indices_list)
        while low < high:
            mid = (low + high) // 2
            if indices_list[mid] < left:
                low = mid + 1
            else:
                high = mid
        return low

    def _find_right_bound(self, indices_list, right):
        low, high = 0, len(indices_list)
        while low < high:
            mid = (low + high) // 2
            if indices_list[mid] <= right:
                low = mid + 1
            else:
                high = mid
        return low
← Back to All Questions