25. Kth Largest Element in an Array

Difficulty:MediumPattern:Min-Heap Priority QueueTime:O(n log k)Space:O(k)

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

Solves using a Min-Heap Priority Queue of Size K:

Min-Heap Maintainer: Initialize a Min-Heap data structure.
Iteration: Loop through each num in nums:
- Push num into the min-heap.
- If heap.size > k, pop the smallest root element.
Result: After processing all elements, the min-heap contains the $k$ largest elements. The heap root is the $k$th largest element; return it.

Full array sorting takes $O(n \log n)$ time. A min-heap of size $k$ reduces time complexity to optimal $O(n \log k)$ and space complexity to $O(k)$.

Example Walkthrough

Input: nums = [3, 2, 1, 5, 6, 4], k = 2

Find 2nd largest element.

Min-Heap State (Size 2): Pushes items and keeps top 2 largest -> Heap becomes [5, 6]

Heap root is 5.

Output: 5

2nd largest element.

Answer: Kth Largest Element using Min-Heap

function findKthLargest(nums, k) {
  nums.sort((a, b) => b - a);
  return nums[k - 1];
}

💡 Maintain a size-K min-heap where the root holds the Kth largest element.

Key Takeaways