K-th Score Leaderboard
Problem
An arcade machine shows a single number on its screen: the k-th highest score ever recorded. It starts with the scores in initial, and then new scores arrive one by one in stream.
After each new score is recorded, the screen updates. Return the list of numbers the screen shows, one per score in stream. Equal scores count separately.
Example 1
- Input:
- k = 3, initial = [50, 20, 80], stream = [60, 10, 90]
- Output:
- [50, 50, 60]
After 60 the scores are 80, 60, 50, 20 → 3rd is 50. After 10 nothing in the top 3 changes → 50. After 90: 90, 80, 60 → 60.
Example 2
- Input:
- k = 1, initial = [], stream = [4, 2, 7]
- Output:
- [4, 4, 7]
Constraints
- 1 ≤ k ≤ 10^4
- 0 ≤ initial.length ≤ 10^4, 1 ≤ stream.length ≤ 10^4
- -10^4 ≤ scores ≤ 10^4
- After each score from stream is added there are at least k scores recorded.
Hint
Show the first hint
Scores below the current top k can never come back into it. Do you need to remember them?
Walkthrough
How to approach it
01Clarify before coding
- Do equal scores count separately? Yes, two 50s occupy two positions.
- Can there be fewer than k scores when we report? No, the constraints guarantee at least k after each addition, though initial alone may have fewer.
- Is this a class in disguise? Yes: a constructor (k, initial) and an add(score) method returning the k-th largest. We model it as a list of results.
02Brute force
Append each new score to a list, sort the whole list descending and read index k - 1.
Cost: O(m · N log N) for m stream scores and up to N total scores: around 10^4 sorts of 2·10^4 values, roughly 3·10^9 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.