Heaps and top-k

For when you need the extreme rather than the whole ordering.

Trigger in the prompt: 'k largest', 'k closest', 'median of a stream', 'merge k sorted things'.

easyKth Largest Element in a Stream

Maintain the k-th largest value as new numbers arrive.

Trigger

'Stream' plus 'k-th largest' — the top-k reflex.

Approach
  1. A min-heap capped at size k. Its root is exactly the k-th largest.
  2. On add: push, and if the size exceeds k, pop the smallest.
  3. Say why a min-heap and not a max-heap: I need cheap access to the weakest candidate.
Target complexity

O(log k) per add, O(k) space.

Pitfall

Keeping every element. The point of the pattern is that space stays O(k) regardless of stream length.

Say it out loud

“The counterintuitive bit is using a min-heap for the k *largest*. The reason is that the thing I need to check cheaply is the weakest candidate I'm holding, so I know who to evict. Space stays O(k) no matter how long the stream runs.”

Solve on LeetCode
mediumDivide Intervals Into Min Groups

Find the minimum number of groups so that no two intervals in a group overlap.

Trigger

'Minimum rooms', 'maximum simultaneous' — this is Meeting Rooms II.

Approach
  1. Reframe: the answer is the maximum number of intervals overlapping at any instant.
  2. Sort by start; keep a min-heap of end times. Pop everything that ended before the current start, then push the current end.
  3. The answer is the maximum heap size seen.
  4. Alternative: a sweep line of +1/−1 events, sorted by time.
Target complexity

O(n log n) time, O(n) space.

Pitfall

Sorting by end instead of start. The heap then no longer models simultaneous occupancy.

Say it out loud

“The answer is the peak number of simultaneously active intervals. Sorting by start and keeping a min-heap of end times models exactly that: the heap size is the current occupancy, and its maximum is the answer.”

Solve on LeetCode
mediumK Closest Points to Origin

Return the k points nearest the origin.

Trigger

'k closest', 'k nearest'.

Approach
  1. Compare squared distances — no need for the square root, and it avoids float error.
  2. Max-heap of size k (negate for Python's min-heap), or quickselect for O(n) average.
  3. Say both and pick: heap for streaming, quickselect for a fixed array.
Target complexity

O(n log k) with the heap, O(n) average with quickselect.

Pitfall

Computing actual square roots. It costs time and introduces floating point comparison issues.

Say it out loud

“I'll compare squared distances — the ordering is identical and it avoids both the square root and float precision. For the selection, a heap of size k is n log k; quickselect gets linear average if the whole array is available up front.”

Solve on LeetCode
mediumKth Largest Element in an Array

Find the k-th largest element in an unsorted array.

Trigger

'k-th largest' on a fixed array — the quickselect question.

Approach
  1. Sorting is O(n log n). The heap is O(n log k). Say both, then offer quickselect.
  2. Quickselect: partition like quicksort, but recurse into only one side.
  3. The cost is n + n/2 + n/4 + … = 2n, so linear on average.
  4. Random pivot, otherwise sorted input degrades to O(n²).
Target complexity

O(n) average, O(n²) worst case; O(1) extra space.

Pitfall

Forgetting the random pivot. It is the difference between linear and quadratic on adversarial input.

Say it out loud

“The heap answer is n log k, but I don't need the array sorted — only one position resolved. Quickselect partitions and descends into a single side, so the work halves each time and the total is linear on average. I'll use a random pivot, otherwise sorted input makes it quadratic.”

Solve on LeetCode
mediumTask Scheduler

Find the minimum time to run all tasks with a cooldown between identical tasks.

Trigger

'Cooldown', 'minimum time with a gap between repeats'.

Approach
  1. Simulation with a heap works and is worth describing.
  2. The closed form is better: the most frequent task defines the skeleton.
  3. (maxCount − 1) × (n + 1) + (number of tasks tied at maxCount), floored at len(tasks).
  4. Explain the floor: with enough distinct tasks there is no idle time at all.
Target complexity

O(n) with the formula, O(n log n) with the heap simulation.

Pitfall

Omitting the max with len(tasks). With many distinct tasks the formula underestimates.

Say it out loud

“The most frequent task sets the skeleton: it has to repeat with gaps, and everything else fills the gaps. That gives a closed form. The one guard is taking the max with the total task count, because with enough distinct tasks there are no idle slots and the formula would undercount.”

Solve on LeetCode
mediumTop K Frequent Elements

Return the k most frequent values in an array.

Trigger

'Top k', 'k most frequent'.

Approach
  1. Count with a Counter — that part is O(n).
  2. Then three options, in increasing cleverness: sort O(n log n); a min-heap of size k, O(n log k); bucket sort by frequency, O(n).
  3. Bucket sort works because frequency is bounded by n, so it can index an array.
Target complexity

O(n) with buckets, O(n log k) with the heap.

Pitfall

Sorting all the counts. It is correct but it is the answer that scores lowest of the three.

Say it out loud

“Counting is linear. For the selection I'd normally use a min-heap of size k, which is n log k. But here frequency is bounded by n, so I can bucket by frequency and read off the top — that's linear, and it's the answer I'd give.”

Solve on LeetCode
hardFind Median from Data Stream

Maintain the median of numbers as they arrive.

Trigger

'Median' plus 'stream' — the two-heaps question.

Approach
  1. Two heaps: a max-heap for the lower half, a min-heap for the upper half.
  2. Invariant: sizes differ by at most one, and every element in the low heap is <= every element in the high heap.
  3. Add: push to one, then move its top across, then rebalance sizes. Doing it in that order keeps the ordering invariant automatically.
  4. Median: the larger heap's root, or the average of both roots.
Target complexity

O(log n) per insertion, O(1) per query, O(n) space.

Pitfall

Rebalancing sizes without first transferring across, which breaks the ordering invariant.

Say it out loud

“Two heaps facing each other: a max-heap of the lower half and a min-heap of the upper. The insertion order matters — I push, then move the top across, then rebalance the sizes. Doing it that way keeps both invariants without extra checks.”

Solve on LeetCode
hardMerge k Sorted Lists

Merge k sorted linked lists into one sorted list.

Trigger

'Merge k sorted things'.

Approach
  1. Naive: concatenate and sort — O(N log N), and it throws away the existing order.
  2. Heap of k pointers: pop the smallest, advance that list, push its successor.
  3. Alternative with the same bound: pairwise merging, log k rounds of O(N).
  4. In Python, push tuples of (value, list_index, node) so ties never compare nodes.
Target complexity

O(N log k) time, O(k) space with the heap.

Pitfall

In Python, pushing (value, node) tuples. On a tie the heap tries to compare nodes and raises.

Say it out loud

“A heap of size k holding the current head of each list gives me n log k rather than n log n. In Python I'd push a tuple with the list index as a tiebreaker, otherwise equal values make the heap try to compare the node objects and it throws.”

Solve on LeetCode