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]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment