K-th Smallest in a Range
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an integer array a (which never changes) and queries, answer each query [l, r, k] with the k-th smallest
value of a[l..r] (0-based, both ends inclusive, k counted from 1; equal values are counted separately). Return the
answers in query order.
Examples
| a | queries | result |
|---|---|---|
[5, 1, 4, 2, 3] | [[0, 4, 2], [1, 3, 3], [2, 2, 1], [0, 2, 3]] | [2, 4, 4, 5] |
[2, 2, 1, 2] | [[0, 3, 1], [0, 3, 2], [1, 2, 2]] | [1, 2, 2] |
Example 1 — the whole array sorted is [1, 2, 3, 4, 5]; [1, 4, 2] sorted is [1, 2, 4]; and so on.
Example 2 — duplicates count separately: [1, 2, 2, 2].
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(a: int[], queries: int[][]) → int[]
Constraints
-
a.length -
a[i] -
queries.length queries[q] = [l, r, k], ,
Expected complexity
- Time
- O((N + Q) log N)
- Space
- O(N log N)
Examples
| a | queries | Expected |
|---|---|---|
[5,1,4,2,3] | [[0,4,2],[1,3,3],[2,2,1],[0,2,3]] | [2,4,4,5] |
[2,2,1,2] | [[0,3,1],[0,3,2],[1,2,2]] | [1,2,2] |
Hint
Hint
Compress values to ranks and think of a segment tree that counts how many elements have each rank; walking down ("go left if
the left count is at least k, otherwise subtract and go right") finds the k-th value in . Keep one such tree per
prefix a[0..i-1] as a persistent segment tree (each version copies only one root-to-leaf path), and walk
T_{r+1} - T_l for the range. A merge sort tree or wavelet tree also works. Per-query selection is and exceeds the time
limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 318 ms | estimated |
| C++ (GCC, gnu++23) | 318 ms | derived |
| Python 3.13 | 2576 ms | derived |
| Java 25 | 2126 ms | derived |
| Kotlin 2.4 (JVM) | 1636 ms | estimated |
| C# 14 (.NET 10) | 1636 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |