How often a value shows up between two places
RangeCounter(arr) keeps the array arr.
count(left, right, value) returns how many times value appears among arr[left], arr[left + 1], ..., arr[right].
There can be many calls on a long array, so walking through the range on every call is too slow for the largest tests: aim for O(log n) per call.
- Input
["RangeCounter","count","count","count"]
[[[4,9,4,4,2,9]],[0,3,4],[1,5,9],[4,4,7]]- Output
[null,3,2,0]
Places 0 to 3 hold 4, 9, 4, 4: three 4s. Places 1 to 5 hold both 9s. Place 4 holds a 2, not a 7.
Limits
1 <= arr.length <= 1000001 <= arr[i], value <= 100000 <= left <= right < arr.lengthat most 20000 calls to count
Hints
Hint 1
In the constructor, list the places where each value appears. Reading the array from the start makes every list sorted.
Hint 2
The count is the number of places in that list from left to right: two binary searches.
Where this was reported
- Amazon, SDE-1 interview, 2025 (LeetCode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
