← Index

Heap

Kth Largest Element in an ArrayMedium

Find the kth largest element in an unsorted array — kth largest in sorted order, not the kth distinct value.

Examples

Approach

Sorting the whole array descending and taking index k-1 works, but it's doing more work than necessary when k is much smaller than n — you don't need the other elements fully ordered. A min-heap capped at size k does better: push every value in, and whenever the heap grows past size k, pop the smallest. What's left in the heap are always the k largest values seen so far, and its top is the answer.

Complexity — best & worst case

Code

// Find the kth largest element in an unsorted array (kth largest in
// SORTED ORDER, not the kth distinct value).

// --- Brute force: sort descending, take index k-1 ---
function findKthLargestSort(nums, k) {
  return [...nums].sort((a, b) => b - a)[k - 1];
}

// --- Better: min-heap of size k ---
// Keep only the k largest values seen so far in a min-heap. If a new
// value beats the smallest of those k (the heap's top), swap it in.
// The heap never grows past size k, so this beats a full sort when
// k is much smaller than n.
class MinHeap {
  constructor() {
    this.values = [];
  }
  insert(value) {
    this.values.push(value);
    let idx = this.values.length - 1;
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);
      if (this.values[idx] >= this.values[parent]) break;
      [this.values[idx], this.values[parent]] = [this.values[parent], this.values[idx]];
      idx = parent;
    }
  }
  extractMin() {
    const min = this.values[0];
    const last = this.values.pop();
    if (this.values.length) {
      this.values[0] = last;
      let idx = 0;
      while (true) {
        const left = 2 * idx + 1;
        const right = 2 * idx + 2;
        let smallest = idx;
        if (left < this.values.length && this.values[left] < this.values[smallest]) smallest = left;
        if (right < this.values.length && this.values[right] < this.values[smallest]) smallest = right;
        if (smallest === idx) break;
        [this.values[idx], this.values[smallest]] = [this.values[smallest], this.values[idx]];
        idx = smallest;
      }
    }
    return min;
  }
  peek() {
    return this.values[0];
  }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.insert(num);
    if (heap.values.length > k) heap.extractMin(); // drop the smallest, keep top k
  }
  return heap.peek();
}

// --- Example Usage ---
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));         // 5
console.log(findKthLargestSort([3, 2, 1, 5, 6, 4], 2));     // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4