Kth largest in a stream
A game's leaderboard shows one number: the score at rank k, meaning the kth largest score recorded so far. Scores keep arriving, and the board must update after each one.
Write a class KthLargest:
KthLargest(k, nums)receiveskand the listnumsof scores recorded so far. It may hold fewer thankscores, or many more. Do not changenums.add(val)takes one more score,val, and returns the score that now sits at rankk.
The kth largest is the score at position k, counting from 1, when every score is sorted from largest to smallest. Repeated scores count separately: with scores 6, 6, 4, the second largest is 6. Every call to add leaves at least k scores recorded.
KthLargest(2, [5, 1, 7]), then add(3), add(8), add(6), add(9)Output5, 7, 7, 8After add(3) the scores from largest are 7, 5, 3, 1, so the second largest is 5. The 8 makes it 7. The 6 lands below the 7, so it stays 7. The 9 makes it 8.
KthLargest(3, [4, 4]), then add(4), add(6), add(6), add(7)Output4, 4, 4, 6Repeats count separately. After the second 6 the scores are 6, 6, 4, 4, 4, so the third largest is still 4. After the 7 they start 7, 6, 6, so it is 6.
KthLargest(1, []), then add(-3), add(-5), add(2)Output-3, -3, 2With k = 1 the answer is the largest score so far. Scores can be negative.
1 ≤ k ≤ 104
0 ≤ len(nums) ≤ 105
-105 ≤ nums[i], val ≤ 105
At most 3 × 104 calls to
add.At least
kscores are recorded after eachadd.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.