Difficulty: Medium Pattern: Heap / Priority Queue LeetCode: https://leetcode.com/problems/kth-largest-element-in-an-array/
PriorityQueue default).Given an integer array nums and an integer k, return the k-th largest element in the array
(1-indexed), counting duplicates separately. You must not sort the array.
Signature:
int findKthLargest(int[] nums, int k)
Examples:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5 # sorted desc: 6,5,4,3,2,1 ; 2nd largest is 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4 # sorted desc: 6,5,5,4,3,3,2,2,1 ; 4th largest is 4
Picture a recruiter with a desk that only fits K resumes, reading from a tall pile. Once the desk is full, every new resume only stays if it beats the weakest one on the desk – and if it does, the weakest goes in the trash to make room. When the pile is done, the weakest survivor left on the desk is the K-th best overall. This problem is that story with “best = largest number”; the “pile” is the whole array, all read in one pass.
To make “drop the weakest of the current K” cheap we use a min-heap – a container whose top is always the smallest item inside it. We keep its size at exactly K and store the K largest values seen so far. Because the top is the smallest of those K, the top is the K-th largest overall; when a new value arrives that beats it, we pop the top (the weakest survivor) and push the new value. This is the size-K heap trick: keep only K items, evict the worst when full. It costs O(n log k), which beats sorting the whole array (O(n log n)) whenever K is small – exactly why the problem tells you not to sort.
The one idea that takes a moment: for “K-th largest” we use a min-heap (min on top), not a max-heap. The reason is the desk analogy – the value we want to throw away is the smallest of the K survivors, so that is the value that must sit on top, ready to pop. A max-heap would put the largest survivor on top and polling it would discard the very value we want to keep.
Smallest trace. Take nums = [3,2,1,5,6,4], k = 2. Walk the array, keeping a min-heap of size
| Step | x | heap after push (top first) | size > 2? | heap after poll | why |
|---|---|---|---|---|---|
| 1 | 3 | {3} | no | {3} | not full yet |
| 2 | 2 | {2,3} | no | {2,3} | size = 2 = K, full |
| 3 | 1 | {1,2,3} | yes | {2,3} | evict 1 (smallest) |
| 4 | 5 | {2,3,5} | yes | {3,5} | evict 2 |
| 5 | 6 | {3,5,6} | yes | {5,6} | evict 3 |
| 6 | 4 | {4,5,6} | yes | {5,6} | evict 4 |
After the scan, the heap holds the two largest values {5, 6}; the top (5) is the smallest of them,
so it is the 2nd largest. This is byte-for-byte the body of add from
0703 - Kth Largest Element in a Stream – the streaming
cousin of this problem – run inside a loop. The same size-K heap trick also drives
0347 - Top K Frequent, where the heap stores value-frequency pairs.
Pause and pick before expanding. A wrong first guess teaches more than a fast right one.
Q1 (recall). Why does “k-th largest” use a min-heap of size k (not a max-heap)?
Q2 (comprehend). Why is this solution O(N log k) and not O(N log N)?
function findKthLargest(nums, k):
create an empty min-heap
for each value x in nums:
push x into the heap
if heap size > k:
remove the smallest from the heap
return the smallest element now in the heap # the k-th largest
import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) {
heap.poll();
}
}
return heap.peek();
}
}
PriorityQueue<Integer> defaults to a min-heap, so poll() always removes the smallest value –
the one we do not want to keep among the top k. The heap never grows past k+1, so each offer/poll
pair is O(log k). After the loop the heap holds exactly the k largest values, and peek() returns
their minimum, i.e. the k-th largest overall. This is byte-for-byte the body of add from LC 703
run inside a loop.
Time: O(N log k) -- N inserts, each costing at most log(k+1) because the heap is capped at k+1
Space: O(k) -- the heap holds at most k elements
Trace nums = [3,2,1,5,6,4], k = 2. The heap is shown as a sorted view (root on the left).
| Step | x | heap after push | size > 2? | heap after poll | survivors (sorted) | |
|---|---|---|---|---|---|---|
| 1 | 3 | {3} | no | {3} | [3] | |
| 2 | 2 | {2,3} | no | {2,3} | [2,3] | |
| 3 | 1 | {1,3,2} | yes | {2,3} | [2,3] | (evict 1) |
| 4 | 5 | {2,3,5} | yes | {3,5} | [3,5] | (evict 2) |
| 5 | 6 | {3,5,6} | yes | {5,6} | [5,6] | (evict 3) |
| 6 | 4 | {4,6,5} | yes | {5,6} | [5,6] | (evict 4) |
Final heap = {5,6}, root = 5. Return 5. (The two largest values are 6 and 5; 5 is the 2nd largest.)
Q1 (apply). Trace nums = [7, 1, 9], k = 2. What is returned?
Q2 (analyze). Suppose you deleted the if (heap.size() > k) poll() line. On nums = [3,2,1,5,6,4], k = 2, what would peek() return?
Q3 (transfer). The note mentions quickselect as an O(N) average alternative. In one sentence, what idea does quickselect use that a heap does not?
poll would throw away
the very element you need.size > k cap, letting the heap grow to N and silently degrading to O(N log N).[3,2,1,5,6,4] with k=2 answers 5, not 2.Arrays.sort the k-th largest lives at index
N - k, not k - 1. (Sorting is forbidden here anyway, and is O(N log N).)Note on alternatives: the quickselect algorithm solves this in O(N) average time and O(1) space by partially partitioning the array around a pivot until the k-th largest lands in place. It is the interview-best answer when k varies and N is large. The heap version is shown here because it teaches the transferable size-K pattern that also solves 703, 347, and 973.
add at a time.