Kth Largest Element in an Array

Intuition

If we only ever keep the k largest values we have seen, then the smallest of those k is exactly the kth largest overall. A min-heap makes that smallest element cheap to inspect because it always sits at the root. We scan the array, pushing every value into the heap, and whenever the heap grows past size k we pop the current minimum, discarding a value that can never be the answer. After the full scan the heap holds the top k values and its root is the kth largest. A Quickselect partition scheme can also solve this in O(n) average time, but the heap approach is simpler to reason about and streams naturally.

Algorithm walkthrough

1. 1Create an empty min-heap that will hold at most k elements.
2. 2For each value in nums, push it onto the heap.
3. 3If the heap size now exceeds k, pop the root (the current minimum) so only the k largest remain.
4. 4The popped value is too small to be among the top k, so discarding it is safe.
5. 5After processing every element, the heap contains the k largest values.
6. 6Return the root of the heap, which is the smallest of those k and therefore the kth largest.

Implementation

import heapq
from typing import List

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