Funcia
Lv.2heappriority-queue

Kth Largest in a Stream

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

kscoresresult
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

  • 1≤1 \le scores.length ≤200,000\le 200{,}000, 0≤0 \le scores[i] ≤109\le 10^9
  • 1≤1 \le k ≤200,000\le 200{,}000 (k may exceed scores.length)

Expected complexity

Time
O(N log K)
Space
O(K)

Examples

kscoresExpected
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: O(log⁡k)O(\log k) per score. Re-sorting everything on every arrival exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251506 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.