Top 12 Heap Interview Problems: Every Pattern, One List

Heap interview problems show up in roughly one out of every six technical rounds. Not because your interviewer has a heap shrine at home. Because the heap answers a suspiciously wide class of questions that all sound different but fundamentally aren't: "give me the best k things," "balance two halves," "merge many sorted streams." Five patterns. Twelve problems. Know them cold and most heap questions stop being surprises.

The Five Patterns That Cover Everything

Every heap problem fits one of five families. Recognizing the family is half the problem. If you see a heap question and you can't name which of these it is, you're going to spend 30 minutes reinventing a wheel you didn't know you owned.

Pattern	Core idea	Typical complexity
Top-K	Min-heap of size k	O(n log k)
Two Heaps	Balance max-heap + min-heap	O(log n) per operation
Greedy + Heap	Always pick the best available item	O(n log n)
Multi-way Merge	Merge k sorted streams	O(n log k)
Interval + Heap	Sort events, track state	O(n log n)

heap-data-structure covers the underlying structure if you need a refresher. For the pattern-first view, top-k-heap-pattern is worth reading first.

---

Medium

1. Kth Largest Element in an Array (LC 215)

What it teaches: The min-heap-of-size-k trick. Keep a min-heap capped at k elements. When it exceeds k, pop the smallest. Whatever sits at the top after processing all elements is the kth largest.

import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

The counterintuitive part: to find the kth largest, use a min-heap. Yes, that feels wrong every single time. The size constraint does the filtering. Time O(n log k), space O(k). When k is small relative to n, this beats sorting by a lot.

The interviewer will almost certainly ask for a follow-up. Quickselect gives you O(n) average. Know both paths.

2. K Closest Points to Origin (LC 973)

What it teaches: Top-K with a custom key. Same pattern as 215, but you rank by squared Euclidean distance instead of raw value.

def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
    heap = []
    for x, y in points:
        dist = x * x + y * y
        heapq.heappush(heap, (-dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

Two things to know cold. First, never take the square root: it wastes CPU and introduces float precision issues. Second, the negation trick turns Python's min-heap into a max-heap, which you need to keep the k closest rather than k farthest. Python's heapq only does min-heaps. The classic workaround: negate your values, feel vaguely criminal, and move on.

3. Top K Frequent Elements (LC 347)

What it teaches: Count first, then apply Top-K. The pattern is two-phase: build a frequency map, then run a min-heap of size k over (count, element) pairs.

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

The O(n log k) heap solution beats O(n log n) sorting when k is small. If the interviewer asks for O(n), sketch bucket sort: index buckets by frequency, scan from the end.

O(n log k) won't give you glowing eyes, but it's enough to feel smug when k is small.

4. Meeting Rooms II (LC 253)

What it teaches: Interval scheduling with a heap. Sort intervals by start time, use a min-heap of end times. When the next meeting starts, check whether the earliest-ending room is free. If yes, reuse it; if no, add a new room.

import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

The heap size at the end equals the minimum number of rooms needed. heapreplace is a single atomic pop-push that avoids an unnecessary heap restructure. The heap always exposes the earliest-ending active meeting at its top.

5. Reorganize String (LC 767)

What it teaches: Greedy with a max-heap. The strategy: always place the most frequent remaining character, unless it was the last one placed. Hold the previously placed character aside for one round to prevent adjacent duplicates.

from collections import Counter
import heapq

def reorganizeString(s: str) -> str:
    count = Counter(s)
    heap = [(-freq, char) for char, freq in count.items()]
    heapq.heapify(heap)
    result = []
    prev_freq, prev_char = 0, ""
    while heap:
        freq, char = heapq.heappop(heap)
        result.append(char)
        if prev_freq < 0:
            heapq.heappush(heap, (prev_freq, prev_char))
        prev_freq, prev_char = freq + 1, char
    return "".join(result) if len(result) == len(s) else ""

If the heap empties while prev_freq still has a count to restore, the string can't be reorganized and you return "". The length check at the end catches this cleanly.

6. Task Scheduler (LC 621)

What it teaches: Greedy scheduling with a cooldown queue. Each cycle you pick the most frequent available task. If nothing qualifies, you idle. The max-heap models "most frequent available," and a cooldown queue holds tasks that are in their n-period wait.

from collections import Counter, deque
import heapq

def leastInterval(tasks: list[str], n: int) -> int:
    count = Counter(tasks)
    heap = [-c for c in count.values()]
    heapq.heapify(heap)
    time = 0
    queue = deque()
    while heap or queue:
        time += 1
        if heap:
            cnt = 1 + heapq.heappop(heap)
            if cnt < 0:
                queue.append((cnt, time + n))
        if queue and queue[0][1] == time:
            heapq.heappush(heap, queue.popleft()[0])
    return time

There is a closed-form formula: max(total_tasks, (max_freq - 1) * (n + 1) + count_of_max_freq). Know the formula as a sanity check, but derive the simulation in the interview. If you blank on the formula under pressure, the heap version always works.

7. Kth Smallest Element in a Sorted Matrix (LC 378)

What it teaches: Multi-way merge on a 2D structure. Each row is sorted, so treat the matrix as n sorted lists and extract the kth minimum using a heap.

import heapq

def kthSmallest(matrix: list[list[int]], k: int) -> int:
    n = len(matrix)
    heap = [(matrix[i][0], i, 0) for i in range(n)]
    heapq.heapify(heap)
    for _ in range(k - 1):
        val, row, col = heapq.heappop(heap)
        if col + 1 < n:
            heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
    return heapq.heappop(heap)[0]

The heap stores (value, row_index, col_index). Each pop advances only that row's pointer, leaving all others unchanged. O(k log n) total. Binary search on the value range also works in O(n log(max - min)) and sometimes surprises interviewers.

8. Find K Pairs with Smallest Sums (LC 373)

What it teaches: Lazy heap expansion. You have two sorted arrays and want the k pairs with smallest sums. Don't enumerate all pairs. Start with (nums1[i], nums2[0]) for the first min(k, len(nums1)) rows, then expand along the j-axis only when you pop.

import heapq

def kSmallestPairs(nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
    heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, len(nums1)))]
    heapq.heapify(heap)
    result = []
    while heap and len(result) < k:
        s, i, j = heapq.heappop(heap)
        result.append([nums1[i], nums2[j]])
        if j + 1 < len(nums2):
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
    return result

The lazy expansion pattern is the key insight here. You only visit O(k log k) pairs in the worst case instead of O(len1 * len2). This same pattern appears in matrix problems, multi-list problems, and occasionally system design questions about merging sorted streams.

---

Hard

The hard problems share exactly one discipline that separates candidates who get them from candidates who don't: state the invariant you're maintaining before you write a single line of code. Out loud. To the interviewer. Like a person who has thought about this before.

Merge K Sorted Lists in a nutshell: the heap does the merging, you just complain that everyone isn't already sorted.

9. Find Median from Data Stream (LC 295)

What it teaches: The two-heap technique. A max-heap holds the lower half, a min-heap holds the upper half. After every insertion, rebalance so sizes differ by at most 1.

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []  # max-heap (negate values)
        self.upper = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lower, -num)
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def findMedian(self) -> float:
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2

This is the most-asked hard heap problem. The two-step insertion (push to lower, immediately rebalance via upper) is elegant but non-obvious the first time you see it. Trace through inserting 1, 2, 3, 4 by hand before your interview. The invariant is: lower always has the same count as upper or one more.

10. Merge K Sorted Lists (LC 23)

What it teaches: Multi-way merge, the canonical version. Push the head of each list into a min-heap. Pop the minimum, advance that list's pointer, push the next node.

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode(0)
    current = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

The i index as a tiebreaker is not optional. Without it, Python attempts to compare ListNode objects when values are equal, which raises a TypeError. This exact bug trips candidates who've studied the algorithm but never run the code. O(n log k) where n is total nodes.

11. IPO (LC 502)

What it teaches: Two-heap greedy. Projects have capital requirements and profits. You want to run at most k projects to maximize total capital. Sort projects by capital required, use a max-heap of profits for what you can currently afford.

import heapq

def findMaximizedCapital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
    locked = sorted(zip(capital, profits))
    unlocked = []
    i = 0
    for _ in range(k):
        while i < len(locked) and locked[i][0] <= w:
            heapq.heappush(unlocked, -locked[i][1])
            i += 1
        if not unlocked:
            break
        w -= heapq.heappop(unlocked)
    return w

Always do the highest-profit currently affordable project. The greedy choice is safe because completing a project only increases your capital, which can only unlock more options. Sort the capital requirements once; scan once; the heap does the rest. See greedy-algorithm for the formal argument behind this kind of greedy validity proof.

12. Smallest Range Covering Elements from K Lists (LC 632)

What it teaches: Multi-source sliding window with a heap. You need a range that includes at least one element from each of k sorted lists, with the range as small as possible.

import heapq

def smallestRange(nums: list[list[int]]) -> list[int]:
    heap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(heap)
    current_max = max(row[0] for row in nums)
    result = [-float('inf'), float('inf')]
    while heap:
        current_min, i, j = heapq.heappop(heap)
        if current_max - current_min < result[1] - result[0]:
            result = [current_min, current_max]
        if j + 1 == len(nums[i]):
            break
        next_val = nums[i][j + 1]
        heapq.heappush(heap, (next_val, i, j + 1))
        current_max = max(current_max, next_val)
    return result

The heap always exposes the current minimum. The current maximum is tracked separately because it can only move upward. When any list is exhausted, no future state can include all k lists, so you stop immediately. If this shows up in your interview, sketch the invariants first before touching a keyboard. "I maintain a window where the minimum is the heap top and the maximum is tracked separately. I shrink from below by popping." That sentence writes the code for you.

---

Problem Map

Problem	Pattern	Difficulty	Key trick
Kth Largest Element (215)	Top-K	Medium	Min-heap of size k
K Closest Points (973)	Top-K	Medium	Negate for max-heap
Top K Frequent (347)	Top-K + Count	Medium	Count first, then heap
Meeting Rooms II (253)	Interval	Medium	Min-heap of end times
Reorganize String (767)	Greedy	Medium	Hold prev char aside
Task Scheduler (621)	Greedy + Cooldown	Medium	Cooldown queue
Kth Smallest in Matrix (378)	Multi-merge	Medium	Treat rows as k lists
K Pairs Smallest Sums (373)	Lazy expansion	Medium	Expand j axis on pop
Find Median from Stream (295)	Two Heaps	Hard	Rebalance invariant
Merge K Sorted Lists (23)	Multi-merge	Hard	Tiebreaker index
IPO (502)	Greedy + Two Heaps	Hard	Unlock then greedy
Smallest Range (632)	Multi-merge + Window	Hard	Max tracked separately

Which Heap Interview Problems to Practice First

One week: 215, 295, 23, 973. Those four cover the Top-K trick, the two-heap invariant, and multi-way merge. Most heap questions are variations on one of those three.

Two weeks: add 347, 253, 621, and 373. That fills in frequency-counting, interval scheduling, greedy scheduling, and lazy expansion. At that point you've seen every major pattern at least twice.

The hard problems (295, 23, 502, 632) share one discipline: state the invariant you're maintaining before writing a single line. "The lower heap always has the same or one more element than the upper heap" is the kind of sentence that writes the code for you. Practice saying it out loud. SpaceComplexity lets you do exactly that with rubric-based feedback on whether your spoken reasoning actually matches your code.

For the pattern-recognition side, heap-problems-leetcode has worked examples with complexity analysis. And for the structural question of when to reach for a heap versus a sorted array, heap-vs-sorted-array has the direct comparison.

Further Reading

• Python heapq documentation, official API with examples, including the nlargest and nsmallest shortcuts
• Wikipedia: Heap (data structure), formal definitions and complexity proofs for heap operations
• GeeksforGeeks: Binary Heap, structural walkthrough with diagrams
• Tech Interview Handbook: Heap cheatsheet, concise pattern summary with time complexities
• LeetCode Heap tag, full problem set sorted by acceptance rate and frequency