A plant-floor report wants the kth-hottest sensor reading from last night’s closed dump — not a live overlay, not a class that keeps answering. The first version copied the log, sorted descending, and took index k - 1. A bench file with a dozen ticks painted instantly. A weekend dump with tens of thousands of readings was still ranking every loser when the overnight job lagged a cycle.

Kth Largest Element in an Array asks for the kth largest of a frozen list. A heap of size k already gives that floor. Sorting the whole array uses that answer and still ranks numbers you throw away.

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 — then we stop. Kth Largest in a Stream is the surviving-class cousin: same size-k min-heap, a class that outlives one call.

The problem

Given an int[] nums and an int k, return the kth largest element — equals occupy distinct seats, so two eights both count. The kth largest is the value that would sit at index k - 1 after a descending sort, not the kth distinct value. The array is frozen: one answer, no later arrivals.

nums = [11, 6, 19, 2, 15], k = 2  →  15    // 19, 15, 11, 6, 2
nums = [11, 6, 19, 2, 15], k = 3  →  11
nums = [8, 8, 3],          k = 2  →  8     // two eights occupy two seats

Note: If they asked for the kth largest after every add, you need a surviving class. That is Kth Largest in a Stream. This prompt answers once.

Sort descending and index k-1 is the honest brute force

Copy the array so the caller’s order survives, sort it, and return the value k from the high end. Arrays.sort is ascending, so that seat is n - k — the same cell as index k - 1 after a descending pass. Correct, and slow in n log n when you only needed k winners.

int kthLargestSort(int[] nums, int k) {
    int[] copy = Arrays.copyOf(nums, nums.length);
    Arrays.sort(copy);
    return copy[copy.length - k];
}

At a dozen values this is a rounding error. At tens of thousands you paid a full sort for a question a size-k heap answers while it walks the array once: what is the smallest of the k largest?

Note: Sorting nums in place is the same answer if they allow mutation. Copying is the safer board default when the prompt did not say you may overwrite.

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 array.

  • Offer the next 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.
  • When the walk finishes, peek is the answer.

You never sort the whole array. You never keep the losers. A value below the current floor is offered, then immediately polled — after the last number the heap is already the answer.

k = 3, nums = [11, 6, 19, 2, 15]

offer 11     heap [11]
offer 6      heap [6, 11]
offer 19     heap [6, 11, 19]
offer 2      heap [2, 6, 11, 19]   size 4 > 3, poll 2
             heap [6, 11, 19]
offer 15     heap [6, 11, 19, 15]  size 4 > 3, poll 6
             heap [11, 15, 19]     peek=11

Same array, k = 2: 2, then 6, then 11 poll out; peek is 15. Duplicates take two seats, they do not collapse:

k = 2, nums = [8, 8, 3]

offer 8     heap [8]
offer 8     heap [8, 8]
offer 3     heap [3, 8, 8]   size 3 > 2, poll 3
            heap [8, 8]      peek=8

The Java is that walk. Natural order makes the root the smallest resident. No class. No later add.

int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int n : nums) {
        heap.offer(n);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
}

Time is O(n log k) — one offer (and maybe a poll) per value. 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 array 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. Sorting the whole array is the same extra bill in a different costume: O(n log n) to rank values whose only job is to miss the cut.

Note: peek assumes the heap is non-empty. The prompt usually promises 1 ≤ k ≤ n. At the board, ask; do not invent a sentinel.

What interviewers usually poke next

  • Quickselect. Partition until the pivot lands at index n - k (or k - 1 on a descending view). Average O(n), worst O(n²) on a bad pivot streak. The partition lives on Quicksort — name it, do not rewrite Hoare at this board. The heap is the usual default when they said “heap” or k is tiny next to n.
  • k = 1. A scan for the max. A heap of size 1 is the same idea with extra ceremony; say you noticed.
  • k = n. A scan for the min. Same observation from the other end. Do not sort n values to return the smallest.
  • Duplicates. They are ordinary values. Two eights both occupy slots if they sit among the k largest. This is not a unique-key ranking.
  • Why sort-all is extra. A full sort ranks every loser you were going to throw away. The heap only ranks against the current floor.
  • Stream cousin. Kth Largest in a Stream is the same size-k min-heap inside a surviving class. This prompt is one-shot. Do not solve the stream here.
  • Not Top K Frequent. That heap ranks by count. This heap ranks by value. Same size-k shape, different question.
  • Last Stone Weight. Smash loop on a max-heap, not a kth ranking. Do not solve it here.
  • K Closest Points to Origin. Size-k winners by distance, not by value. Same family, different question.

You are done with this problem when you can say, out loud, why sorting descending is correct, why a size-k min-heap’s peek is the kth largest, and why Quickselect is the linear-average follow-up you do not owe unless they ask.