6.1 Top K Elements

Demo: Kth Largest Element in an Array — LC 215 (Medium — Amazon/Meta/Google High)

Statement (Demo): Given an integer array nums and an integer k, return the k-th largest element in sorted order (not the k-th distinct). Example: nums=[3,2,1,5,6,4], k=2 → 5 | ⚡ 1 ≤ k ≤ n ≤ 10⁵, -10⁴ ≤ nums[i] ≤ 10⁴

Approach: JavaScript has no built-in heap, so write a small MinHeap once — every heap pattern (6.x, Dijkstra in 8.6) reuses it. Keep a min-heap of the k largest seen so far: push each number, and when the size passes k, pop the smallest. The top is then the k-th largest.

class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.data = [];
    this.compare = compare;
  }
  get size() {
    return this.data.length;
  }
  peek() {
    return this.data[0];
  }
  push(value) {
    const d = this.data;
    d.push(value);
    let i = d.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(d[i], d[parent]) >= 0) break;
      [d[i], d[parent]] = [d[parent], d[i]]; // sift up
      i = parent;
    }
  }
  pop() {
    const d = this.data;
    const top = d[0];
    const last = d.pop();
    if (d.length) {
      d[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1,
          r = l + 1;
        let smallest = i;
        if (l < d.length && this.compare(d[l], d[smallest]) < 0) smallest = l;
        if (r < d.length && this.compare(d[r], d[smallest]) < 0) smallest = r;
        if (smallest === i) break;
        [d[i], d[smallest]] = [d[smallest], d[i]]; // sift down
        i = smallest;
      }
    }
    return top;
  }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop(); // drop the smallest — keep the k largest
  }
  return heap.peek();
}

Complexity: Time O(n log k), Space O(k) (quickselect gives O(n) average — mention it as a follow-up)