Kth Largest Element in an Array | Leetcode 215

Welcome to our deep dive on Kth Largest Element in an Array (Leetcode 215). This is a classical problem that evaluates your knowledge of Priority Queues (Heaps) versus standard sorting algorithms.

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element. You must solve it in O(n) time complexity optimally (though O(N log K) is also widely accepted).

Example: nums = [3,2,1,5,6,4], k = 2 => Output: 5

Approach 1: Min-Heap (Priority Queue) O(N log K)

Instead of explicitly sorting the entire array in O(N log N), we can maintain a "Top K" list using a Min-Heap.

A Min-Heap always keeps the absolute smallest element at the root (top) of the heap.

1. We iterate through every number in nums.
2. We push the number into our Min-Heap.
3. If the size of our Min-Heap strictly exceeds k, we simply pop the root element. Because it's a Min-Heap, we are popping the smallest element currently in the heap!
4. By doing this, we elegantly discard all the smaller elements. At the end of the loop, the Heap will contain exactly the K largest elements from the array. The root of the heap (the smallest of those K giants) is our answer!

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        
        for num in nums:
            heapq.heappush(min_heap, num)
            
            # Keep the heap strictly size K
            if len(min_heap) > k:
                heapq.heappop(min_heap)
                
        # The root is strictly the Kth largest
        return min_heap[0]

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (215)