Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2080.html
2080. Range Frequency Queries (Medium)
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.
Implement the RangeFreqQuery
class:
RangeFreqQuery(int[] arr)
Constructs an instance of the class with the given 0-indexed integer arrayarr
.int query(int left, int right, int value)
Returns the frequency ofvalue
in the subarrayarr[left...right]
.
A subarray is a contiguous sequence of elements within an array. arr[left...right]
denotes the subarray that contains the elements of nums
between indices left
and right
(inclusive).
Example 1:
Input ["RangeFreqQuery", "query", "query"] [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] Output [null, 1, 2] Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.
Constraints:
1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
- At most
105
calls will be made toquery
Companies:
Quora
Related Topics:
Array, Binary Search
Solution 1. Binary Search
Initialization: For each unique value in A
, store its corresponding indices in a map m
.
Query:
- If
value
doesn’t exist in the original array, return0
. - Otherwise, let
v = m[value]
– the array of all the indices ofvalue
in the original array - Let
j
be the first index thatv[j] > right
. - Let
i
be the first index thatv[i] >= left
. - The answer is
j - i
.
-
// OJ: https://leetcode.com/problems/range-frequency-queries/ // Time: // RangeFreqQuery: O(N) // query: O(log(N)) // Space: O(N) class RangeFreqQuery { unordered_map<int, vector<int>> m; // map from a value to all its indices public: RangeFreqQuery(vector<int>& A) { for (int i = 0; i < A.size(); ++i) m[A[i]].push_back(i); } int query(int left, int right, int value) { if (m.count(value) == 0) return 0; // `value` doesn't exist in the original array auto &v = m[value]; // `v` is the array of all the indices of `value` in the original array int j = upper_bound(begin(v), end(v), right) - begin(v); // Find the first index `j` that `v[j] > right`. int i = lower_bound(begin(v), end(v), left) - begin(v); // Find the first index `i` that `v[i] >= left`. return j - i; // The answer is `j - i` } };
-
class RangeFreqQuery: def __init__(self, arr: List[int]): self.mp = defaultdict(list) for i, x in enumerate(arr): self.mp[x].append(i) def query(self, left: int, right: int, value: int) -> int: if value not in self.mp: return 0 arr = self.mp[value] l, r = bisect_right(arr, left - 1), bisect_right(arr, right) return r - l # Your RangeFreqQuery object will be instantiated and called as such: # obj = RangeFreqQuery(arr) # param_1 = obj.query(left,right,value) ############ # 2080. Range Frequency Queries # https://leetcode.com/problems/range-frequency-queries/ class RangeFreqQuery: def __init__(self, arr: List[int]): self.mp = collections.defaultdict(list) for i, x in enumerate(arr): self.mp[x].append(i) def query(self, left: int, right: int, value: int) -> int: a = bisect.bisect_left(self.mp[value], left) b = bisect.bisect_right(self.mp[value], right) return b - a # Your RangeFreqQuery object will be instantiated and called as such: # obj = RangeFreqQuery(arr) # param_1 = obj.query(left,right,value)
-
class RangeFreqQuery { private Map<Integer, List<Integer>> mp = new HashMap<>(); public RangeFreqQuery(int[] arr) { for (int i = 0; i < arr.length; ++i) { mp.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i); } } public int query(int left, int right, int value) { if (!mp.containsKey(value)) { return 0; } List<Integer> arr = mp.get(value); int l = search(arr, left - 1); int r = search(arr, right); return r - l; } private int search(List<Integer> arr, int val) { int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) >> 1; if (arr.get(mid) > val) { right = mid; } else { left = mid + 1; } } return left; } } /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery obj = new RangeFreqQuery(arr); * int param_1 = obj.query(left,right,value); */
-
type RangeFreqQuery struct { mp map[int][]int } func Constructor(arr []int) RangeFreqQuery { mp := make(map[int][]int) for i, v := range arr { mp[v] = append(mp[v], i) } return RangeFreqQuery{mp} } func (this *RangeFreqQuery) Query(left int, right int, value int) int { arr := this.mp[value] l := sort.SearchInts(arr, left) r := sort.SearchInts(arr, right+1) return r - l } /** * Your RangeFreqQuery object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,value); */
Discuss
https://leetcode.com/problems/range-frequency-queries/discuss/1589028/C%2B%2B-Straightforward-Binary-Search