LeetCode 215: Kth Largest Element In An Array — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Heap | Array | Divide and Conquer | Priority Queue

The Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in sorted order, not the kth distinct element.

Approach

Use a min-heap of size k to maintain the k largest elements seen so far. As we iterate through the array, we add each element to the heap and remove the smallest element if the heap size exceeds k. The root of the min-heap will be the kth largest element.

Time: O(n log k) · Space: O(k)

Code

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []

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

        return min_heap[0]