Kth Largest Element in a Stream

1. The obvious way

   Keep every number, sort on each add: O(n log n) per call.

2. The key insight

   Keep a min-heap of at most k numbers. In add: push the value, pop the smallest if there are more than k, and return the top. Each call is O(log k).

3. The algorithm
   1. Constructor: keep k, push all starting numbers while trimming to k.
   2. add: push the value.
   3. If more than k numbers, pop the smallest.
   4. Return the heap top.

Watch it run

podium: 4, 5, 8

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.podium = []                              # min-heap of the k largest so far
        for number in nums:
            self.add(number)

    def add(self, val):
        heapq.heappush(self.podium, val)
        if len(self.podium) > self.k:
            heapq.heappop(self.podium)                # the weakest steps down
        return self.podium[0]                         # the edge of the podium

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.