Optimal Python Solution for Kth Largest Element in an Array (Interview Script)

2025-10-02

The Logic

• Sorting the entire array does unnecessary work.
• A heap lets us keep track of only the k largest elements.
• Use a min heap of size k so the smallest element in the heap is the kth largest overall.

Implementation / Diagram

Key Invariant

The heap always contains the k largest elements seen so far, with the smallest of them at the top.

import heapq

def findKthLargest(nums, k):
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]