Given an integer array and a number k, return the k-th largest element. It is the k-th largest in sorted order, not the k-th distinct value.
DSA Animator › DSA Revision › Heap / Priority Queue › Kth Largest Element in an Array
Remember: for the k largest, use a min heap of size k. The root of that heap is the k-th largest. The video solves Kth Largest Element in an Array (LeetCode 215, Medium) with the Min Heap of Size K pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive Kth Largest Element in an Array animation.
Given an integer array and a number k, return the k-th largest element. It is the k-th largest in sorted order, not the k-th distinct value.
For 3, 2, 1, 5, 6, 4 with k equal to 2, the answer is 5. Sorted from largest, the values are 6, 5, 4, 3, 2, 1, and the second one is 5.
Sorting the whole array and picking index n minus k works in O of n log n. But we only care about the top k values, not the full order.
Keep a min heap that holds at most k numbers. It always stores the k largest numbers seen so far. The smallest of those k sits at the root, so the root is the k-th largest so far. For every new number, push it, and if the heap grows beyond k, poll the root. At the end, the root is the answer.
Push 3, then 2, and the heap holds 2 and 3. Push 1, and the size becomes 3, so poll the smallest, which is 1. Push 5, and poll 2, so the heap holds 3 and 5. Push 6, and poll 3, so the heap holds 5 and 6. Push 4, and poll 4 itself, because it is the smallest of the three. The heap holds 5 and 6, and the root, 5, is the answer.
In code, create a min priority queue. For each number, offer it. If the size is greater than k, poll. Return the peek. Each operation costs O of log k, so the total is O of n log k, with O of k space.
Remember: for the k largest, use a min heap of size k. The root of that heap is the k-th largest.