1097. Kth Smallest in Ranges
A school records exam scores in nums, one per student in seating order. A teacher sends many queries [a, b, k] about the block of students seated from position a to position b (both included, and the two positions may arrive in either order). Let m be the number of students in that block. Sort their scores in ascending order and report the score at 0-based index k mod m of that sorted list; so k = 0 is the lowest score and k = m - 1 the highest, while larger k wrap around.
Equal scores are separate entries (a block of scores 4, 4, 9 sorted is 4, 4, 9). Return one score per query, in query order. The scores never change, but there are many queries, so sorting every block from scratch is too slow.
Example 1
- Input:
- nums = [8,3,5,3,9]queries = [[0,4,0],[0,4,4],[1,3,1],[4,2,2],[1,3,4]]
- Output:
- [3,9,3,9,3]
- Explanation:
The whole row sorted is 3, 3, 5, 8, 9, giving the minimum 3 and the maximum 9; block 1..3 sorted is 3, 3, 5; the reversed pair (4, 2) is the block 9, 5, 3 sorted as 3, 5, 9; and k = 4 on three students wraps to index 1.
Example 2
- Input:
- nums = [6,6,1], queries = [[0,1,1],[0,2,2],[2,2,7]]
- Output:
- [6,6,1]
- Explanation:
Duplicates occupy separate positions: block 6, 6 has index 1 equal to 6; block 1, 6, 6 has index 2 equal to 6; a single student answers with their own score whatever
kis.
Constraints
1 ≤ nums.length ≤ 40000
1 ≤ queries.length ≤ 40000, and every query has exactly three integers [a, b, k]
0 ≤ a, b < nums.length (a may be larger than b); 0 ≤ k ≤ 109
-109 ≤ nums[i] ≤ 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 + q) log n)
- Space
- O(n log n)