Kth Largest Element in an Array

Why it belongs on this sheet

This problem is the reusable heap version of top-k selection and shows up constantly in interview prep.

Pattern

Min-heap of size k

Approach

Maintain a min-heap containing the largest k elements seen so far. Once the scan ends, the heap top is the kth largest.

Java solution

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();
  }
}

Complexity

• Time: O(n log k)
• Space: O(k)

Interview note

Quickselect is a good follow-up, but the heap answer is usually the safest first explanation.