Quiz League Final Cutoff

MediumheapAlso known as Kth Largest Element in a Stream

A pub quiz league sends its best k teams to a grand final. Teams finish their seasons on different nights, and each one's season total is posted as soon as it is final. Wrong answers cost a point, so a total can be negative.

The league website shows one number: the cutoff, meaning the total you currently need to be in the top k. It has to update the moment each new total arrives, all season long.

Your task

Write a class FinalCutoff:

constructor(k, totals): k is the number of final places; totals is the list of totals already posted (it may be empty).
add(total): record one more posted total, then return the k-th highest total posted so far. If fewer than k totals have been posted, return null (None in Python).

Equal totals take separate places: if the top totals are 50, 50 and 40, the 2nd highest is 50 and the 3rd is 40.

class FinalCutoff

Examples

Example 1

Input

new FinalCutoff(3, [42, 17, 30])
.add(25)
.add(50)
.add(10)
.add(42)

Output

[null, 25, 30, 30, 42]

Why

Top 3 starts as 42, 30, 17. Adding 25 knocks out 17: top 3 is 42, 30, 25, cutoff 25. Adding 50 knocks out 25: cutoff 30. Adding 10 is too low to matter: still 30. Adding 42 knocks out 30: top 3 is 50, 42, 42, cutoff 42.

Example 2

Input

new FinalCutoff(2, [])
.add(-5)
.add(8)
.add(3)

Output

[null, null, -5, 3]

Why

With one total posted there is no 2nd place yet, so the answer is null. After 8 arrives the top 2 is 8, -5, so the cutoff is -5. Then 3 pushes -5 out: cutoff 3.

Constraints

1 ≤ k ≤ 10,000
0 ≤ totals.length ≤ 10,000
-1,000 ≤ each total ≤ 1,000
At most 10,000 calls to add.

Start with brute force

Keep every total in a list. On each add, append, sort from high to low, and read position k - 1.

Each call costs O(n log n) where n is everything posted so far. With 10,000 starting totals and 10,000 calls, each sort handles 10,000 to 20,000 totals, so the season costs about 2 billion steps. Keeping the list sorted by inserting in place is better, but shifting elements still costs O(n) per call.

Hints

0 of 4 shown

Hint 1
In the first example, after the top 3 is 42, 30, 25, a total of 10 arrives. Does any total below the current cutoff ever matter again, now or later?
Hint 2
Once a total falls out of the top k, it can never come back: new totals only push the bar up. So you only ever need to keep k totals.
Hint 3
Among the k totals you keep, the answer is the smallest one. When a new total arrives, you compare it with that smallest one and maybe replace it. Which data structure gives you the smallest item and lets you swap it out in O(log k)?
Hint 4
Keep a min-heap of at most k totals. To add: push the total, and if the heap now holds more than k, pop the smallest. If the heap holds exactly k, its top is the answer; otherwise return null. Load the starting totals the same way.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

You never need the whole league, only the current top k. Among those, the one that matters is the weakest, because it is the cutoff and the first to be pushed out. A min-heap of size k keeps exactly that weakest one on top.

Trace the first example with k = 3:

Start: push 42, 17, 30. Heap holds 17, 30, 42 (17 on top).
add 25: push, heap has 4 items, pop the smallest (17). Heap: 25, 30, 42. Return 25.
add 50: push, pop 25. Heap: 30, 42, 50. Return 30.
add 10: push, pop 10 straight back out. Heap unchanged. Return 30.
add 42: push, pop 30. Heap: 42, 42, 50. Return 42.

Notice the direction: to track the highest totals you use a min-heap. A max-heap would put the champion on top, which is the one total you never need to look at.

Reference solution

class FinalCutoff {
  constructor(k, totals) {
    this.k = k;
    this.heap = []; // min-heap of the k highest totals
    for (const t of totals) this.add(t);
  }
  add(total) {
    const h = this.heap;
    h.push(total); // sift up
    for (let i = h.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (h[p] <= h[i]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
    if (h.length > this.k) { // drop the smallest: move last to top, sift down
      h[0] = h.pop();
      for (let i = 0; ; ) {
        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) break;
        [h[m], h[i]] = [h[i], h[m]];
        i = m;
      }
    }
    return h.length === this.k ? h[0] : null;
  }
}

import heapq
 
class FinalCutoff:
    def __init__(self, k, totals):
        self.k = k
        self.heap = []  # min-heap of the k highest totals
        for t in totals:
            self.add(t)
 
    def add(self, total):
        heapq.heappush(self.heap, total)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)  # drop the smallest
        return self.heap[0] if len(self.heap) == self.k else None

TimeO(log k)Per add: one push and at most one pop on a heap that never holds more than k + 1 items. The constructor costs O(n log k) for n starting totals.

SpaceO(k)Only the top k totals are kept.

Learn the idea: Heaps and Priority Queues Designing Data Structures

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code