Kth Largest Element in an Array

Keep a min-heap of the k largest values seen so far. Push each number; if the heap grows past k, pop its smallest. At the end the heap's top is the k-th largest.

Traced input: nums = [3, 2, 1, 5, 6, 4], k = 2 → 5. Original problem: neetcode.io/problems/kth-largest-element-in-an-array

Complexity

Quickselect is O(n) on average, O(n²) worst case.

Key idea

• The k-th largest is the smallest of the top k values.
• A min-heap of size k keeps exactly those top k, smallest on top.
• When a 6th value arrives for k = 5, the smallest of the six can't be in the top 5: pop it.

Common mistakes

• Using a max-heap of all n values is O(n log n) and O(n) space.
• Sorting is O(n log n); fine to mention, but the heap or quickselect is expected.
• Duplicates count separately: [3, 3, 2], k = 2 gives 3.

Solution

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int i = 0; i < nums.length; i++) {
        heap.offer(nums[i]);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
}

def findKthLargest(nums: List[int], k: int) -> int:
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int x : nums) {
        heap.push(x);
        if ((int)heap.size() > k) {
            heap.pop();
        }
    }
    return heap.top();
}

Edge cases

Each one has its own trace in the interactive view.