1095. Below K in Ranges
A sensor array stores one calibration reading per slot in nums. Technicians send many checks of the form [a, b, k]: how many readings in the slots from position a to position b (both included) are strictly smaller than k? The two positions may arrive in either order, so the stretch is always the one between them, whichever is smaller.
Return an array with one answer per query, in the order the queries were given. Readings may repeat, and k does not have to equal any reading. The array itself never changes between queries, but there are many queries, so scanning every stretch from scratch is too slow.
Example 1
- Input:
- nums = [5,1,4,1,6,3]queries = [[0,5,4],[2,4,5],[3,3,1],[4,1,6]]
- Output:
- [3,2,0,3]
- Explanation:
In the whole array three readings (1, 1, 3) are below 4; the last query swaps its endpoints, so it covers slots 1 to 4 and counts 1, 4, 1 below 6.
Example 2
- Input:
- nums = [2,2,2], queries = [[0,2,2],[0,2,3],[1,1,3]]
- Output:
- [0,3,1]
- Explanation:
Readings equal to
kare not counted (strictly smaller), so the first query is 0, the second counts all three, the third counts one.
Constraints
1 ≤ nums.length ≤ 50000
1 ≤ queries.length ≤ 50000, and every query has exactly three integers [a, b, k]
0 ≤ a, b < nums.length (a may be larger than b)
-109 ≤ nums[i], k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n + q log^2 n)
- Space
- O(n log n)