Typorithm · medium

Kth Largest Element

kth-largest-elementheapsmin-heaptop-kbounded-heap

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Kth Largest Element

Heaps

Keep a min-heap of size k; after processing all numbers, its root is the kth largest element.

Sorting to find the kth largest is O(n log n); a bounded heap does it in O(n log k).

A min-heap of size k always holds the k largest values seen, with the smallest of them at the root.

Whenever the heap grows past k, popping the minimum evicts a value too small to be in the top k.

Min-heap capped at size k.

Pop the minimum when size exceeds k.

Root is the kth largest.

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop();
    }
  }
  return heap.peek();
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Min-heap of size k

A size-k min-heap keeps the k largest seen so far.

const heap = new MinHeap()

2. Offer each value

Every number is considered for the top-k set.

heap.push(num)

3. Evict smallest

When the heap exceeds k, drop the current minimum.

if (heap.size() > k) {
      heap.pop();
    }

4. Kth largest

The heap's minimum is the kth largest overall.

return heap.peek()

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.