Lv.2heappriority-queue
Kth Largest in a Stream
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Scores arrive one by one in the order of scores. After each arrival, report the k-th highest score seen so far (equal
scores count separately), or -1 while fewer than k scores have arrived. Return the reports as an array.
Examples
| k | scores | result |
|---|---|---|
3 | [4, 5, 8, 2, 3, 9, 4] | [-1, -1, 4, 4, 4, 5, 5] |
1 | [3, 1, 7] | [3, 3, 7] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(k: int, scores: int[]) → int[]
Constraints
-
scores.length,scores[i] -
k(kmay exceedscores.length)
Expected complexity
- Time
- O(N log K)
- Space
- O(K)
Examples
| k | scores | Expected |
|---|---|---|
3 | [4,5,8,2,3,9,4] | [-1,-1,4,4,4,5,5] |
1 | [3,1,7] | [3,3,7] |
Hint
Hint
Keep only the top k scores in a min-heap; its minimum is the answer. Push each score and pop when the heap grows past k:
per score. Re-sorting everything on every arrival exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1506 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |