loading

Kth Largest Element in an Array — Step-by-Step Visualization

mediumLeetCode #215ArrayDivide and ConquerSortingHeap (Priority Queue)Quickselect

Given an integer array `nums` and an integer `k`, return the `k-th` largest element in the array. Note that it is the `k-th` largest element in the sorted order, not the `k-th` distinct element.

Algorithm Pattern

Min-Heap of Size K

Key Idea

To find the Kth largest element, we can maintain a Min-Heap of size K. As we iterate through the array, we add each number to the heap. If the heap size exceeds K, we pop the minimum element. After processing all numbers, the top of the Min-Heap will be the Kth largest element (since the K largest elements are currently in the heap, and the smallest among them is the Kth largest).

Step-by-Step Approach

  1. Initialize an empty Min-Heap.
  2. For each number `n` in `nums`:
  3. Push `n` onto the Min-Heap.
  4. If `heap.size() > k`, pop the smallest element.
  5. Return `heap.peek()`.

Common Gotchas

  • For Kth largest, use a Min-Heap. For Kth smallest, use a Max-Heap.
  • Heap operations (push/pop) are O(log K), making the total time complexity O(N log K).

Related Problems

← All problems