K-th highest latency so far
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
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
kthHighest([40, 10, 50, 30, 60], 2)returns[null, 10, 40, 40, 50]kthHighest([5, 5, 5], 2)returns[null, 5, 5]Equal values count separately.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.
Read the editorial and a reference solution
Sorting everything after each request answers correctly and costs O(n log n) per request. Only the k highest values so far can ever matter, so keep just those.
Hold them in a min-heap. Its top is the smallest of the k highest, which is the k-th highest. When a new latency arrives and the heap is full, it can only change the answer if it beats the top: replace the top with it and sift down. Otherwise nothing changes.
Taking the minimum of the last k values is a different question, the lowest recent value, and it fails as soon as an old high value should still count.
function kthHighest(latencies, k) {
const h = [];
const up = (i) => { while (i > 0) { const p = (i - 1) >> 1; if (h[p] <= h[i]) break; [h[p], h[i]] = [h[i], h[p]]; i = p; } };
const down = (i) => {
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < h.length && h[l] < h[m]) m = l;
if (r < h.length && h[r] < h[m]) m = r;
if (m === i) return;
[h[m], h[i]] = [h[i], h[m]]; i = m;
}
};
return latencies.map((x) => {
if (h.length < k) { h.push(x); up(h.length - 1); }
else if (x > h[0]) { h[0] = x; down(0); }
return h.length < k ? null : h[0];
});
}Complexity. O(n log k) time, O(k) space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.