Top 10 LeetCode Heap Problems for Coding Interviews: Easy to Hard

Every "must-know patterns" list mentions "top-K with a heap." What those lists skip: there are three distinct heap patterns, and only one of them is "put K things in a heap." Drill just the top-K template and you'll walk into LC 295 blank, wonder why your mental model broke, and drop a hard problem that shows up in basically every FAANG loop.

These ten LeetCode heap problems cover all three families, ordered easy to hard within each family. Each one teaches something the previous one doesn't. Work through them in order.

This guide assumes you know what a heap is. The goal is problem-solving fluency, not pattern-matching.

Three Families, One Signal

Top-K: keep a single heap of size K. The root is always the Kth best element you've seen. Problems 1 through 5.

K-way merge: maintain a heap of K active pointers into K sorted sources. Problems 6 and 7.

Two heaps: split a dataset at the median into a max-heap (lower half) and a min-heap (upper half). Problems 8 through 10.

The signal across all three: you need repeated access to the "best" element from a changing set, and re-sorting every time is too slow. If you can identify which family you're in before you start coding, the structure mostly writes itself. This is also where candidates lose points at Google and Meta, not because they get the code wrong, but because they don't recognize the family fast enough to use their time well. The interviewer is already filling in your scorecard while you're still staring at the problem.

Problem 1: Kth Largest in a Stream (LC 703)

Numbers arrive one at a time. After each insertion, return the Kth largest.

The insight: a min-heap of size exactly K holds the K largest values seen so far, and its root is always the Kth largest. When a new number arrives, push it. If the heap exceeds size K, pop the root. Done.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        for n in nums:
            self.add(n)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

This is two lines of logic. You will memorize this. Then, three months later, you'll blank on it under pressure. Drill it until it's reflex. Every other top-K problem builds on this invariant.

Problem 2: Kth Largest in an Array (LC 215)

Same question, static array.

The heap of size K from above works in O(n log k). But for a single rank on a static array, quickselect runs O(n) average, which beats the heap. Know both. If your interviewer asks "can you do better?" after you present the heap solution, that's your cue. It is not a rhetorical question.

Write the heap solution first. Quickselect is the right answer when they push you on complexity.

Problem 3: Top K Frequent Elements (LC 347)

Find the K most frequent values in an array.

Two steps: build a frequency map, then run top-K on the entries. The trap is reaching for a sort at step two. A min-heap of size K gives O(n log k) instead of O(n log n). There is also a bucket sort approach where bucket index equals frequency, hitting O(n), which comes up as a follow-up. Know all three approaches and when each wins.

This problem appears constantly at Google and Meta because the three valid solutions make it easy to keep asking follow-up questions for the rest of the interview. You will answer it. Then they will ask about your time complexity. Then about the bucket approach. Then about large K. Budget accordingly.

Problem 4: K Closest Points to Origin (LC 973)

Given n points, find the K closest to the origin. Same heap-of-size-K structure, but the comparison is on a computed value.

Two lessons. You do not need the square root. Compare x² + y² directly. It avoids floating-point and runs faster. Second, you want a max-heap here: keep the K smallest distances, evict the largest. Python's heapq is a min-heap, so push negated distances. This forces you to think about heap direction, which trips up candidates who learned the LC 703 template and stopped there.

Problem 5: Task Scheduler (LC 621)

Given tasks and a cooldown n, find the minimum CPU intervals to finish all tasks.

You can simulate with a max-heap plus a wait queue tracking when tasks come off cooldown. It works. The cleaner solution is pure math: max(total_tasks, (max_freq - 1) * (n + 1) + count_of_max_freq_tasks).

Present the simulation if you're unsure how to derive the formula. The math is what the problem is actually teaching. If you walk in with the formula memorized and can't explain where it comes from, that's a different kind of problem.

Worth including because it breaks the top-K template in a useful way. Sometimes the heap is a valid path, not the best one.

Problem 6: Merge K Sorted Lists (LC 23)

Merge K sorted linked lists into one. The canonical K-way merge.

Init a min-heap with the first node from each list. Pop the minimum, attach it to the output, push that node's next child. Each of the n total nodes is processed once; each heap op is O(log k). Total: O(n log k).

The naive approach merges two lists at a time: O(nk). When k is large, the difference is the whole interview discussion. You're essentially paying O(n) per merge and doing k-1 merges, so most nodes get touched multiple times. The heap eliminates that.

Python requires a tiebreaker since ListNode objects aren't directly comparable. Push (val, index, node) where index breaks ties. Forgetting this is the kind of bug that surfaces at the very end when you have two nodes with equal values and Python throws a TypeError at you in front of your interviewer.

This problem connects to merge sort's divide-and-conquer structure, but the K-way heap approach is more general and what interviewers want here.

Problem 7: Kth Smallest in a Sorted Matrix (LC 378)

An n×n matrix where each row and column is sorted. Find the Kth smallest element.

You can treat each row as a sorted source and run K-way merge from LC 23. You can also binary search on the answer: pick a midpoint value, count how many elements are ≤ mid in O(n), run O(n log(max - min)) total.

Both are correct. Binary search on the answer is usually what the interviewer wants. This is where problems 6 and 7 diverge. Seeing them back to back is the point: K-way merge is not automatically the answer just because a problem has K sorted sources.

Problem 8: K Pairs with Smallest Sums (LC 373)

Two sorted arrays. Find the K pairs with the smallest sum. Generating all n² pairs and sorting runs O(n² log n) and times out.

Treat this as a state-space BFS. For each row i, the minimum-sum pair is (nums1[i], nums2[0]). Push those initial K states. When you pop (i, j), push (i, j+1) if it exists. You process at most K states, each heap op O(log K). Total: O(K log K).

This is sometimes called directed BFS, which is a fancy name for "only expand states that might actually be useful." It appears across a family of "find K results from a combinatorial space" problems. Most candidates overpopulate the heap upfront or forget to track visited states with a set indexed by (i, j). The second bug is worse because the answer looks plausible until you test an edge case.

Problem 9: Find Median from Data Stream (LC 295)

Numbers arrive one at a time. After each insertion, return the current median.

Two heaps: a max-heap for the lower half, a min-heap for the upper half. The median is the root of the lower heap (odd total) or the average of both roots (even total). On every insert, rebalance so sizes differ by at most one.

Insertion is O(log n). Median query is O(1). The balance invariant is the whole algorithm. Get this clean before you touch problem 10, because problem 10 is the same structure with a harder constraint bolted on top. Rushing ahead is how you end up debugging two things at once.

Problem 10: Sliding Window Median (LC 480)

Same as LC 295, but elements leave the window as it slides.

The heap doesn't support efficient deletion. Naive rebuild on every exit is O(n²). The fix is lazy deletion: when an element leaves the window, mark it in a hash map. When it rises to the top of its heap, skip it. This keeps removal amortized O(log k) per element and the overall algorithm O(n log k).

Lazy deletion sounds like procrastination with a technical name. It kind of is. The insight is that you don't need to remove the element immediately, you just need to not count it when it matters. That delay is free when the element is buried in the heap, and cheap when it finally floats up.

This problem fuses the two-heap invariant with the sliding window pattern and adds lazy deletion. It is the hardest on this list and sits at the staff-level bar. Solve it after the other nine. Lazy deletion is the technique worth carrying to other problems.

All Ten LeetCode Heap Problems at a Glance

#	Problem	LC #	Difficulty	Pattern	What It Teaches
1	Kth Largest in Stream	703	Easy	Top-K	Root of min-heap is Kth largest
2	Kth Largest in Array	215	Medium	Top-K	Quickselect vs heap tradeoff
3	Top K Frequent Elements	347	Medium	Top-K	Count first, select second
4	K Closest Points	973	Medium	Top-K	Max-heap direction, skip sqrt
5	Task Scheduler	621	Medium	Greedy + heap	Math beats the simulation
6	Merge K Sorted Lists	23	Hard	K-way merge	O(n log k) via K-head heap
7	Kth Smallest in Matrix	378	Medium	K-way merge / Binary search	Binary search on the answer
8	K Pairs Smallest Sums	373	Medium	State-space BFS	Expand frontier lazily
9	Find Median from Stream	295	Hard	Two heaps	Balance invariant, O(1) median
10	Sliding Window Median	480	Hard	Two heaps	Lazy deletion for O(log k) removal

Three Things Worth Repeating

A min-heap of size K holds the K largest values seen. Its root is the Kth largest. Problems 1 through 4 are this invariant applied in different contexts.
Quickselect beats the heap for single-rank queries on a static array. O(n) average versus O(n log k). Write the heap first, offer quickselect when pushed on complexity.
Lazy deletion (problem 10) is the transferable technique. Any time a heap needs soft removal of elements that are no longer relevant, it applies. Name it explicitly when you use it. Interviewers write down the things you name.

If you can solve all ten but your reasoning sounds halting when you explain it out loud, that's a different problem. SpaceComplexity runs voice-based mock interviews with rubric scoring, so you find out which dimension is costing you before a real loop does.

Want to go deeper on pattern recognition before you hit the problems? Top-K pattern recognition covers the five signals that tell you a heap is the right tool.