Q66: Kth Largest Element in an Array. - DSA Patterns (Multi-Lang)

In Simple Words: Min-Heap of size $K$. Add elements; when heap size exceeds $K$, pop the minimum. At the end, root of the Min-Heap is guaranteed to be the $K$-th largest element.

Time: $O(N \log K)$ | Space: $O(K)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

import heapq

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