171. Kth Largest Element in an Array

Keep a min-heap holding the k largest elements seen so far. Push each number; whenever the heap grows past k, pop the smallest. The heap's root then holds the kth largest.

Idea

We don't need the whole array sorted — only the kth largest. Maintain a min-heap capped at size k containing the k biggest elements seen so far. Because it's a min-heap, its smallest element (the root) is the weakest of those k — precisely the kth largest overall once every element has been considered.

Algorithm

1. For each num in nums:
   • Push num onto the heap.
   • If the heap size exceeds k, pop the smallest element.
2. After processing all numbers, the heap holds the k largest; return its root heap[0].

Each push/pop is O(log k), and the heap never exceeds k elements.

Worked example: nums = [3,2,1,5,6,4], k = 2

Heap (size ≤ 2) after each push, popping when it exceeds 2:

Root = 5, the 2nd largest.

Complexity

• Time: O(n log k).
• Space: O(k) for the heap.

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }
}