LC-2080 Medium LeetCode

2080. Range Frequency Queries

Array Hash Table Binary Search Design Segment Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 40% Topics: Array, Hash Table, Binary Search, Design, Segment Tree

Reading material

Arrays & Hashing 12 min Binary Search 12 min Design (Data Structures) 14 min

Reference solution (spoiler · python)

# Time:  ctor:  O(n)
#        query: O(logn)
# Space: O(n)

import collections
import bisect


class RangeFreqQuery(object):

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

    def query(self, left, right, value):
        """
        :type left: int
        :type right: int
        :type value: int
        :rtype: int
        """
        return bisect.bisect_right(self.__idxs[value], right) - \
               bisect.bisect_left(self.__idxs[value], left)

Solution from kamyu104/LeetCode-Solutions · MIT