kth-largest-element.ts

import { MinHeap } from "../lib/min-heap.js";

/**
 * 215. Kth Largest Element in an Array  (Medium)
 * Link: https://leetcode.com/problems/kth-largest-element-in-an-array/
 *
 * Return the kth largest element in an unsorted array (the kth largest in
 * sorted order, not the kth distinct element).
 *
 * Example:
 *   Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
 *   Output: 5
 *
 * Approach:
 *   Maintain a min-heap of size k holding the k largest elements seen so far.
 *   Push each number; whenever the heap exceeds size k, pop the smallest. The
 *   root of the final heap is the kth largest. Keeping the heap at size k costs
 *   O(log k) per element rather than O(log n).
 *
 * Time:  O(n log k)
 * Space: O(k)
 */
export function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap<number>((x) => x);

  for (const num of nums) {
    heap.push(num);
    if (heap.size > k) heap.pop();
  }

  return heap.peek()!;
}