Kth Largest Element in an Array

Given an unsorted array and an integer k, return the kth largest element. It is the element that would sit at position len(nums) - k after a descending sort — not necessarily distinct, so duplicates count as separate positions.

The key insight: you do not need to sort the whole array. A min-heap of size k does the job with one pass. The machine pushes each element onto the heap, and the moment the heap exceeds k elements, it pops the smallest. When the pass ends, the heap holds exactly the k largest elements, and its root is the kth largest — the smallest of those k, which is exactly what the problem asks for.

Approach in steps:

1. Build an empty min-heap.
2. For each x in nums, push x; if len(heap) > k, pop the root.
3. Return heap[0].

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

Time is O(n log k), space O(k). The heap never grows past k, so pushes and pops are cheap relative to full sorting.

Trickiest edge case: duplicates. With [3,2,3,1,2,4,5,5,6], k = 4, the answer is 4, not 5 — the heap keeps duplicates as separate entries, and the pop always removes the current minimum, preserving the count of equal values. An alternative is quickselect for O(n) average time, but the heap is deterministic and safe from worst-case pivot behavior.