Kth Largest Element in an Array

Problem in plain words

Given an integer array and a number k, return the value that would be at position k if the array were sorted from largest to smallest. Duplicates count as separate elements, so in [5, 5, 1] the 2nd largest is 5. The challenge is to do better than fully sorting.

Example: nums = [7, 2, 9, 4, 9], k = 3. In descending order the array is 9, 9, 7, 4, 2, so the answer is 7.

Intuition

We only care about the k largest numbers. Keep them in a min-heap of size k: the smallest of the "top k" sits at the root. When a new number arrives, push it; if the heap grows past k, pop the minimum, because that number can no longer be among the top k. After all numbers are processed, the root is the k-th largest. Heap insertions use the bubble-up step, so each costs O(log k).

Approach

1. Create an empty min-heap.
2. For each number, push it onto the heap.
3. If the heap size exceeds k, pop the smallest element.
4. Return the heap's top.

Dry run

nums = [7, 2, 9, 4, 9], k = 3

The top of the heap is 7.

Java solution

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

Python solution

class Solution:
    def findKthLargest(self, 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]

Complexity

Edge cases and common mistakes

• Using a max-heap of everything — pushing all n numbers and popping k − 1 times works but uses O(n) space.
• Removing duplicates — the k-th largest counts duplicates, so do not deduplicate with a set.
• k equal to the array length — the answer is the minimum element; the heap code handles it naturally.
• Negative numbers — no special handling needed; the heap orders them correctly.