A plant-floor overlay wants the kth-hottest sensor reading so far, not the max — operators use that floor to decide whether the line is running hot. The first version stored every sample and sorted on each arrival. A bench test with a dozen ticks painted instantly. A weekend run with tens of thousands of readings was still sorting the whole log when the panel lagged a cycle.

Kth Largest in a Stream asks for the kth largest after every add. A heap of size k already gives the floor of the current winners for free. Sorting the whole history uses that answer and still pays a full sort per tick.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Here we only care about keeping k winners so peek is the kth largest.

The problem

Design a class. The constructor takes an int k and an initial int[] nums. add(val) inserts val into the stream and returns the kth largest among every number seen so far. Equals occupy distinct seats: two nines both count. The kth largest is the value that would sit at index k - 1 after a descending sort — not the kth distinct value.

k = 3, nums = [9, 4, 14, 7]

add(11)  →  9     // stream 9, 4, 14, 7, 11; third largest is 9
add(2)   →  9     // 2 never enters the top three
add(15)  →  11    // 15, 14, 11

Note: If they asked only for the kth largest of a frozen array, a one-shot heap would be enough. This prompt keeps answering after every arrival, so the heap has to survive across calls.

Store every number and sort on add is the honest brute force

Keep a list. The constructor copies nums in. add appends, sorts, and returns the value k from the high end. Correct. Slow in the stream length.

class KthLargestScan {
    final int k;
    final List<Integer> nums = new ArrayList<>();

    KthLargestScan(int k, int[] stream) {
        this.k = k;
        for (int n : stream) {
            nums.add(n);
        }
    }

    int add(int val) {
        nums.add(val);
        Collections.sort(nums);
        return nums.get(nums.size() - k);
    }
}

At a dozen samples this is a rounding error. At tens of thousands of adds you paid a full sort for a question a size-k heap answers with one offer (and maybe a poll): what is the smallest of the k largest?

Size-k min-heap: offer, maybe poll, then peek

PriorityQueue is a min-heap. Root is the smallest resident. Keep at most k numbers — the current winners. The root is then the smallest of those k, which is the kth largest in the stream.

  • Offer the new value.
  • If the heap now holds more than k numbers, poll. That poll drops the floor, so the remaining k are still the largest seen so far.
  • Return peek.

You never sort the history. You never keep the losers. A value below the current floor is offered, then immediately polled.

k = 3, nums = [9, 4, 14, 7]

offer 9     heap [9]
offer 4     heap [4, 9]
offer 14    heap [4, 9, 14]
offer 7     heap [4, 9, 14, 7]   size 4 > 3, poll 4
            heap [7, 9, 14]      peek=7

add(11)     offer 11             [7, 9, 14, 11]
            size 4 > 3, poll 7   [9, 11, 14]      → 9
add(2)      offer 2              [2, 9, 11, 14]
            size 4 > 3, poll 2   [9, 11, 14]      → 9
add(15)     offer 15             [9, 11, 14, 15]
            size 4 > 3, poll 9   [11, 14, 15]     → 11

The Java is that walk. The constructor reuses add so the initial stream is trimmed the same way later arrivals are. Natural order makes the root the smallest resident:

class KthLargest {
    final int k;
    final PriorityQueue<Integer> heap = new PriorityQueue<>();

    KthLargest(int k, int[] nums) {
        this.k = k;
        for (int n : nums) {
            add(n);
        }
    }

    int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

Constructor is O(n log k) — one offer (and maybe a poll) per initial value. Each add is O(log k). Space is O(k) — the heap holds at most k + 1 numbers. Do not re-lecture sift at the whiteboard unless they ask.

Note: A max-heap of the whole stream ranks every loser. Peek there is the largest, not the kth; getting the kth means polling k − 1 winners and putting them back, while you still store numbers you will never return. You only need k winners.

Note: peek assumes the heap is non-empty. The prompt usually promises at least k numbers by the time you must answer. At the board, ask; do not invent a sentinel.

What interviewers usually poke next

  • k = 1. A running max. A heap of size 1 is the same idea with extra ceremony; a single field is enough. Say you noticed.
  • Duplicates. They are ordinary values. Two nines both occupy slots if they sit among the k largest. This is not a unique-key ranking.
  • k larger than the initial stream. Ask. Typical prompts already start with enough numbers, or you still offer everything and the heap stays smaller than k until later adds fill it. Do not peek an empty heap.
  • One-shot array. Kth Largest Element in an Array is the frozen cousin: same size-k min-heap, no surviving class. Do not solve it here.
  • Not Top K Frequent. That heap ranks by count. This heap ranks by value. Same size-k shape, different question.

You are done with this problem when you can say, out loud, why sorting on every add is correct, why a size-k min-heap’s peek is the kth largest, and why a max-heap of the whole stream is the wrong bill.