Pattern Recognition Drill

#142 — Kth Largest Element in an Array

Medium Heaps

The Problem

Find the kth largest element in an unsorted array.

What approach would you use?

Think about it before scrolling down.

Key Signals

Heap / Priority Queue

Min-heap of size k. Push each element; pop if heap > k. Top is kth largest. O(n log k).

Alt: Divide & Conquer

Quickselect: partition and recurse on the relevant half. O(n) average.

Common Trap

A full sort is O(n log n). Quickselect is O(n) average but O(n²) worst case without randomization.

← #141