K-th highest latency so far

MediumAbout 30 minProblem 1 of 2 in HeapsDraft

The problem

A dashboard shows, after each request, the k-th highest latency seen so far: a steadier signal than the single worst request.

Return a list with one entry per request: the k-th highest latency among the requests up to and including it, or null while fewer than k requests have arrived. Equal latencies count separately.

  • 0 ≤ latencies.length ≤ 200,000
  • 1 ≤ k ≤ 1,000

Examples

  1. kthHighest([40, 10, 50, 30, 60], 2)returns [null, 10, 40, 40, 50]
  2. kthHighest([5, 5, 5], 2)returns [null, 5, 5]Equal values count separately.
  3. kthHighest([7, 3], 1)returns [7, 7]

Hints

Hint 1 of 2

Only the k highest values so far matter. Which of them is the answer?

Hint 2 of 2

Keep them in a min-heap of size k. A new latency enters only if the heap has room or it beats the top; the top is then the k-th highest.

Editorial

Opens once you solve the problem, or after three checked attempts.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open