Problem Description

You need to design a data structure that can efficiently find how many times a specific value appears in a given subarray.

The task is to implement a class called RangeFreqQuery with the following functionality:

1. Constructor RangeFreqQuery(int[] arr): Initialize the data structure with a given integer array arr (0-indexed).

2. Query Method query(int left, int right, int value): Return the number of times value appears in the subarray from index left to index right (inclusive).

For example, if you have an array [1, 2, 2, 3, 2, 4] and you query for the value 2 in the range [1, 4], the subarray would be [2, 2, 3, 2], and the frequency of 2 would be 3.

The solution uses a preprocessing approach where during initialization, it creates a hash table that maps each unique value to a list of indices where that value appears in the original array. When a query is made, it uses binary search on the pre-stored index list to quickly find how many indices fall within the given range [left, right]. Specifically, it finds the leftmost position where an index is at least left and the leftmost position where an index is greater than right, then calculates the difference to get the count.

Intuition

The naive approach would be to iterate through the subarray [left, right] for each query and count occurrences of the target value. However, this would take O(n) time per query, which becomes inefficient when we have many queries.

The key insight is that we can preprocess the array to make queries faster. Think about it this way: if we know all the positions where a particular value appears in the array, we can answer any range query about that value quickly.

For instance, if value 2 appears at indices [1, 3, 5, 7, 9], and we want to know how many times it appears in range [2, 8], we just need to count how many of these indices fall within [2, 8]. The indices [3, 5, 7] are within the range, so the answer is 3.

Since the indices for each value are naturally sorted (we traverse the array from left to right during preprocessing), we can use binary search to efficiently find:

• The first index in our list that is >= left (lower boundary)
• The first index in our list that is > right (upper boundary)

The difference between these two positions gives us the count of indices within the range, which equals the frequency of the value in that subarray.

This transforms our problem from "count occurrences in a range" to "count how many pre-stored indices fall within a range", which can be solved in O(log m) time where m is the number of occurrences of the value in the entire array.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The solution uses a Hash Table + Binary Search approach to efficiently answer range frequency queries.

Data Structure Setup

We use a hash table g (implemented as a defaultdict(list)) where:

• Key: Each unique value in the array
• Value: A list of indices where this value appears

During initialization in the constructor:

def __init__(self, arr: List[int]):
    self.g = defaultdict(list)
    for i, x in enumerate(arr):
        self.g[x].append(i)

We iterate through the array once, and for each element x at index i, we append the index i to the list self.g[x]. Since we traverse from left to right, the indices in each list are automatically sorted in ascending order.

Query Implementation

For the query(left, right, value) method:

def query(self, left: int, right: int, value: int) -> int:
    idx = self.g[value]
    l = bisect_left(idx, left)
    r = bisect_left(idx, right + 1)
    return r - l

1. Get the index list: We retrieve idx = self.g[value], which contains all indices where value appears. If the value doesn't exist, idx will be an empty list.

2. Find the left boundary: l = bisect_left(idx, left) finds the leftmost position in idx where we could insert left to maintain sorted order. This gives us the index of the first occurrence that is >= left.

3. Find the right boundary: r = bisect_left(idx, right + 1) finds the leftmost position where we could insert right + 1. This gives us the index of the first occurrence that is > right.

4. Calculate frequency: The difference r - l gives us the count of indices that fall within the range [left, right].

Time Complexity

• Initialization: O(n) where n is the length of the array
• Query: O(log m) where m is the number of occurrences of the queried value
• Space Complexity: O(n) to store all indices in the hash table

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given array: [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]

Step 1: Initialization (Building the Hash Table)

We traverse the array and build our hash table g that maps each value to its list of indices:

Value 12: appears at indices [0, 9]
Value 33: appears at indices [1, 7]
Value 4:  appears at indices [2]
Value 56: appears at indices [3, 11]
Value 22: appears at indices [4, 8]
Value 2:  appears at indices [5]
Value 34: appears at indices [6, 10]

Our hash table g looks like:

g = {
    12: [0, 9],
    33: [1, 7],
    4:  [2],
    56: [3, 11],
    22: [4, 8],
    2:  [5],
    34: [6, 10]
}

Step 2: Query Example - query(left=1, right=8, value=33)

We want to count how many times 33 appears in the subarray from index 1 to 8 (inclusive).

1. Retrieve index list: idx = g[33] = [1, 7]

   • These are all positions where 33 appears in the original array

2. Find left boundary: l = bisect_left([1, 7], 1) = 0

   • We're looking for where to insert 1 in the list [1, 7]
   • Since 1 already exists at position 0, bisect_left returns 0
   • This means the first occurrence of 33 that is >= 1 is at position 0 in our index list

3. Find right boundary: r = bisect_left([1, 7], 9) = 2

   • We're looking for where to insert 9 (which is right + 1 = 8 + 1)
   • 9 would go after 7, at position 2
   • This means there are 2 indices that are <= 8

4. Calculate result: r - l = 2 - 0 = 2

   • Both indices [1, 7] fall within the range [1, 8]
   • Therefore, 33 appears 2 times in the subarray

Step 3: Another Query Example - query(left=5, right=10, value=34)

1. Retrieve index list: idx = g[34] = [6, 10]

2. Find left boundary: l = bisect_left([6, 10], 5) = 0

   • 5 would be inserted at position 0 (before 6)
   • The first index >= 5 is at position 0 in our list

3. Find right boundary: r = bisect_left([6, 10], 11) = 2

   • 11 would be inserted at position 2 (after 10)
   • Both indices are <= 10

4. Calculate result: r - l = 2 - 0 = 2

   • Both indices [6, 10] fall within the range [5, 10]
   • Therefore, 34 appears 2 times in the subarray

Edge Case - Query for non-existent value: query(left=2, right=6, value=99)

1. Retrieve index list: idx = g[99] = [] (empty list, as 99 doesn't exist)
2. Find boundaries: l = 0, r = 0 (both binary searches on empty list return 0)
3. Calculate result: r - l = 0 - 0 = 0 (correctly returns 0)

This approach efficiently answers each query in O(log m) time by leveraging preprocessed data and binary search, rather than scanning through the entire range for each query.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Constructor (__init__): O(n) where n is the length of the input array. The constructor iterates through each element in the array exactly once, and for each element, it appends the index to the corresponding list in the dictionary. The append operation is O(1) amortized, so the total time is O(n).

• Query function (query): O(log m) where m is the number of occurrences of the queried value in the array. The function performs two binary searches using bisect_left on the list of indices for the given value. Each binary search takes O(log m) time. Since we perform two binary searches, the total time is O(log m) + O(log m) = O(log m). In the worst case where all elements in the array are the same value, m = n, so the worst-case time complexity is O(log n).

Space Complexity:

• O(n) where n is the length of the input array. The dictionary self.g stores a list of indices for each unique value in the array. In total, we store exactly n indices across all lists in the dictionary (since each index from 0 to n-1 appears exactly once). Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Right Boundary Calculation

The Pitfall: A common mistake is using bisect_right(indices, right) instead of bisect_left(indices, right + 1) for finding the right boundary. While both might seem to work, they can produce different results in edge cases.

# Incorrect approach that might seem intuitive
def query(self, left: int, right: int, value: int) -> int:
    indices = self.value_to_indices[value]
    left_position = bisect_left(indices, left)
    right_position = bisect_right(indices, right)  # Wrong!
    return right_position - left_position

Why it's wrong:

• bisect_right(indices, right) finds the position after all occurrences of right
• bisect_left(indices, right + 1) finds the position before all occurrences of values > right
• These are equivalent only when right is in the indices list, but differ when it's not

Example demonstrating the issue:

arr = [1, 2, 3, 2, 5, 2]
# indices for value 2: [1, 3, 5]
# Query for value=2 in range [0, 4]

# Using bisect_right(indices, 4): returns 2 (correct by coincidence)
# Using bisect_left(indices, 5): returns 2 (correct)

# But if we query range [0, 3]:
# Using bisect_right(indices, 3): returns 2 (correct)
# Using bisect_left(indices, 4): returns 2 (correct)

# However, if indices were [1, 3, 4, 5] and we query [0, 3]:
# Using bisect_right(indices, 3): returns 2 (wrong - misses index 3)
# Using bisect_left(indices, 4): returns 2 (correct)

2. Not Handling Non-Existent Values

The Pitfall: Forgetting that the queried value might not exist in the original array. Since we use defaultdict(list), this is handled automatically, but with a regular dictionary, this would cause a KeyError.

# Problematic if using regular dict instead of defaultdict
def __init__(self, arr: List[int]):
    self.value_to_indices = {}  # Regular dict
    for index, value in enumerate(arr):
        if value not in self.value_to_indices:
            self.value_to_indices[value] = []
        self.value_to_indices[value].append(index)

def query(self, left: int, right: int, value: int) -> int:
    # This will raise KeyError if value doesn't exist!
    indices = self.value_to_indices[value]  
    # ...

Solution: Either use defaultdict(list) as in the original solution, or add a check:

def query(self, left: int, right: int, value: int) -> int:
    if value not in self.value_to_indices:
        return 0
    indices = self.value_to_indices[value]
    left_position = bisect_left(indices, left)
    right_position = bisect_left(indices, right + 1)
    return right_position - left_position

3. Misunderstanding Binary Search Return Values

The Pitfall: Assuming that bisect_left returns -1 or None when the element isn't found (like some search functions do). In reality, it returns the insertion position that would maintain sorted order.

# Incorrect assumption about bisect_left behavior
def query(self, left: int, right: int, value: int) -> int:
    indices = self.value_to_indices[value]
    left_position = bisect_left(indices, left)
  
    # Wrong: checking if element was "found"
    if left_position == -1 or left_position >= len(indices):
        return 0
  
    # This check is unnecessary and incorrect

Why it works correctly without checks:

• If left is greater than all indices, bisect_left returns len(indices)
• If right + 1 is greater than all indices, bisect_left returns len(indices)
• The subtraction right_position - left_position naturally gives 0 when no indices fall in the range
• The algorithm handles all edge cases automatically through the mathematical properties of the insertion positions