2080. Range Frequency Queries | 1702

 1class RangeFreqQuery:
 2    # intuition
 3    # we need O(1) query
 4    # subarray O(1) lookup makes me think of prefix sums
 5    # e.g., for everything to the left of 1 (inclusive): defaultdict(int) with {12: 1, 33: 1}
 6    # for everything to the left of 2 (inclusive): defaultdict(int) with {12: 1, 33: 1, 4: 1}
 7    # query 4 for [1, 2] means prefix2[4] - prefix0[4]
 8    # NOTE: this intuition MLEs, it is O(n^2) memory
 9
10    def __init__(self, arr: List[int]):
11        self.n = len(arr)
12        self.hash_list = [None] * self.n
13
14        self.hash_list[0] = defaultdict(int)
15        self.hash_list[0][arr[0]] += 1
16        for i in range(1, self.n):
17            temp_dict = self.hash_list[i - 1].copy()
18            temp_dict[arr[i]] += 1
19            self.hash_list[i] = temp_dict
20
21    def query(self, left: int, right: int, value: int) -> int:
22        if left == 0:
23            return self.hash_list[right][value]
24        return self.hash_list[right][value] - self.hash_list[left - 1][value]
25
26
27# Your RangeFreqQuery object will be instantiated and called as such:
28# obj = RangeFreqQuery(arr)
29# param_1 = obj.query(left,right,value)

 1class RangeFreqQuery:
 2    # intuition #2
 3    # for each value, store a sorted list of indices where it appears
 4    # e.g., 33: [1, 7]
 5    # we can realize this structure in O(nlogn) with priority queue
 6    # NOTE: we actually don't need pq at all - since we traverse from left to right, .append promises sorted state
 7    # then, two binary search for each query solves it
 8
 9    def __init__(self, arr: List[int]):
10        self.d = defaultdict(list)
11        for i, value in enumerate(arr):
12            self.d[value].append(i)
13
14    def query(self, left: int, right: int, value: int) -> int:
15        return bisect_right(self.d[value], right) - bisect_left(self.d[value], left)
16
17
18# Your RangeFreqQuery object will be instantiated and called as such:
19# obj = RangeFreqQuery(arr)
20# param_1 = obj.query(left,right,value)