Heap & Stack Patterns: 8 Interview Problems Solved

Most people fail heap problems in interviews not because they don’t know what a heap is, but because they can’t recognize when to use one. The moment an interviewer says “find the k-th largest” or “merge k sorted lists,” your brain should immediately jump to heapq — not sorting, not a nested loop. The difference between O(n log k) and O(n log n) is the difference between a pass and a fail at a FAANG-tier interview.

This post solves 8 real interview problems using heap and monotonic stack patterns, building the mental model first before touching any code.

How to Recognize Heap vs Stack Problems

The intuition: a min-heap lets you always access the smallest element in O(1), and remove it in $O(\log n)$. A max-heap does the inverse. The core invariant is the heap property: for a min-heap, every parent satisfies $parent \leq children$. For a complete binary tree of $n$ nodes, insertions and deletions are $O(\log n)$, and peek is $O(1)$.

Why does this matter? When you need the “top k” of anything — k-th largest, k closest points, k most frequent — you’re looking at a bounded priority queue. Keep a heap of size k and you only ever process $O(n \log k)$ operations instead of sorting the whole array.

$$T(n, k) = O(n \log k) \quad \text{where } k \ll n$$

Monotonic stacks are different. They answer questions about “next greater” or “next smaller” elements. The stack stays sorted (either non-decreasing or non-increasing) by popping elements that violate the property. You process each element at most twice (push once, pop once), giving you $O(n)$ total.

The mental test I use: if the problem involves ordering by value over a sliding window or stream, it’s likely a heap. If it involves relative order and nearest comparisons, it’s likely a monotonic stack.

Problems 1–4: Heap Patterns

Problem 1: K-th Largest Element in a Stream

Classic. LeetCode 703. The naive approach is to sort on every insertion — $O(n \log n)$ per call. With a min-heap of size k, each insertion is $O(\log k)$ and we always have the k-th largest at the top.

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = []  # min-heap of size k
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)  # remove the smallest
        return self.heap[0]  # k-th largest is heap min

# Trace through k=3, nums=[4,5,8,2]
# Init step by step:
#   push 4 -> heap=[4]
#   push 5 -> heap=[4,5]
#   push 8 -> heap=[4,5,8]
#   push 2 -> heap=[2,4,5,8], len=4 > k=3, pop min(2) -> heap=[4,5,8]
# After init: heap=[4,5,8]
#
# add(3):  push 3  -> [3,4,5,8] -> pop min(3) -> [4,5,8],   return 4
# add(5):  push 5  -> [4,5,5,8] -> pop min(4) -> [5,5,8],   return 5
# add(10): push 10 -> [5,5,8,10] -> pop min(5) -> [5,8,10], return 5
# add(9):  push 9  -> [5,8,9,10] -> pop min(5) -> [8,9,10], return 8
# add(4):  push 4  -> [4,8,9,10] -> pop min(4) -> [8,9,10], return 8

kth = KthLargest(3, [4, 5, 8, 2])
print(kth.add(3))   # 4
print(kth.add(5))   # 5
print(kth.add(10))  # 5
print(kth.add(9))   # 8
print(kth.add(4))   # 8

The gotcha: Python’s heapq is a min-heap only. For a max-heap, negate the values (heapq.heappush(heap, -val)). This trips people up under pressure.

Problem 2: K Closest Points to Origin

Given a list of points and an integer k, return the k closest points to the origin. Distance formula:

$$d(p) = \sqrt{x^2 + y^2}$$

But you don’t need sqrt for comparisons — comparing $x^2 + y^2$ directly is faster and avoids float precision issues.

Two approaches: sort in $O(n \log n)$ or maintain a max-heap of size k in $O(n \log k)$. The heap wins when $k \ll n$. For small inputs, sort-based approaches can be competitive due to cache efficiency and Python’s Timsort constant factors — but for streaming inputs or k much smaller than n, the heap is the right choice.

import heapq
from typing import List

def k_closest(points: List[List[int]], k: int) -> List[List[int]]:
    # Max-heap: store (-distance, x, y) so largest dist gets popped first
    heap = []

    for x, y in points:
        dist = -(x*x + y*y)  # negated for max-heap behavior
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # evict the farthest point

    return [[x, y] for _, x, y in heap]

points = [[1,3],[-2,2],[5,8],[0,1]]
print(k_closest(points, 2))  # [[-2,2],[0,1]] — distances: 10, 8, 89, 1

Alternative: heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2). It’s cleaner for one-shot queries but rebuilds from scratch each time — not suitable if points arrive in a stream.

Problem 3: Merge K Sorted Lists

LeetCode 23. The naive O(n·k) approach compares k list heads at every step. A min-heap reduces that to $O(n \log k)$ where n is total nodes.

import heapq
from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def __lt__(self, other):  # needed for heapq to compare nodes
        return self.val < other.val

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, node)

    dummy = ListNode(0)
    curr = dummy

    while heap:
        node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, node.next)

    return dummy.next

The __lt__ override is the kind of thing that seems obvious in hindsight but causes a TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' at runtime if you forget it. Python’s heapq requires elements to be comparable — it doesn’t fall back to identity comparison to avoid subtle, non-deterministic ordering bugs.

Problem 4: Task Scheduler

LeetCode 621. This one’s subtle. Given tasks with a cooldown n, find the minimum time to finish all tasks. The greedy insight: always schedule the most frequent remaining task. That’s a max-heap.

from collections import Counter, deque
from typing import List
import heapq

def least_interval(tasks: List[str], n: int) -> int:
    counts = Counter(tasks)
    # Max-heap (negated values)
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)

    time = 0
    cooldown_queue = deque()  # (available_time, count)

    while heap or cooldown_queue:
        time += 1

        if heap:
            count = heapq.heappop(heap) + 1  # +1 because negated; -3 becomes -2
            if count < 0:  # still tasks remaining for this type
                cooldown_queue.append((time + n, count))

        if cooldown_queue and cooldown_queue[0][0] == time:
            heapq.heappush(heap, cooldown_queue.popleft()[1])

    return time

print(least_interval(["A","A","A","B","B","B"], 2))  # 8
# Sequence: A B _ A B _ A B

The space complexity here is $O(|\Sigma|)$ where $|\Sigma|$ is the alphabet size (at most 26), not O(n). The heap never grows beyond 26 elements. Worth mentioning in an interview.

Problems 5–8: Monotonic Stack Patterns

Problem 5: Next Greater Element

LeetCode 496. For each element, find the next element in another array that’s larger. The brute force is $O(n \cdot m)$. A monotonic stack with a hashmap is $O(n + m)$.

The stack stays monotonically decreasing. When you hit a value larger than the stack top, that larger value is the “next greater” for the top element.

from typing import List

def next_greater_element(nums1: List[int], nums2: List[int]) -> List[int]:
    next_greater = {}  # val -> next greater val in nums2
    stack = []  # monotonic decreasing stack

    for num in nums2:
        # Pop everything the current number is greater than
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # Anything left in stack has no next greater -> -1
    for leftover in stack:
        next_greater[leftover] = -1

    return [next_greater[n] for n in nums1]

print(next_greater_element([4,1,2], [1,3,4,2]))  # [-1,3,-1]
# Trace: process 1 -> stack=[1]
#        process 3 -> 3>1, pop 1: next_greater[1]=3, stack=[3]
#        process 4 -> 4>3, pop 3: next_greater[3]=4, stack=[4]
#        process 2 -> 2<4, push: stack=[4,2]
#        leftover: 4->-1, 2->-1

Problem 6: Daily Temperatures

LeetCode 739. For each day, how many days until a warmer temperature? Classic monotonic stack on indices.

from typing import List

def daily_temperatures(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # stack of indices, monotonically decreasing by temperature

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)

    return result

temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1,1,4,2,1,1,0,0]

Each index is pushed once and popped at most once: $O(n)$ total, $O(n)$ space for the stack in the worst case (strictly decreasing temperatures like [5,4,3,2,1]).

Problem 7: Largest Rectangle in Histogram

LeetCode 84. This is where monotonic stacks get genuinely interesting. For each bar, find the widest rectangle that uses that bar as the shortest.

Here’s the key insight: you maintain an increasing stack of indices. When you hit a bar shorter than the top, the top bar can’t extend further right — compute its rectangle.

from typing import List

def largest_rectangle_area(heights: List[int]) -> int:
    stack = []  # indices, increasing height order
    max_area = 0

    # Sentinel 0 at the end forces all remaining bars to be processed
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # Width extends from current i to element below in stack
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # 10
# The rectangle of height 5 and width 2 (bars at index 2 and 3)

The + [0] sentinel is the kind of trick that feels hacky but is completely intentional. Without it, you’d need a separate loop to drain the stack — the sentinel forces the while-loop to handle everything. The sentinel sits at index len(heights), one past the last real bar. When the stack is empty during a pop, width = i (= len(heights)) correctly gives full-array width, because the popped bar is the minimum of everything seen so far.

The area formula is:

$$A = h \times (i – \text{stack[-1]} – 1)$$

where the subtraction of 1 accounts for the fact that stack[-1] is the index of the element to the left that blocked leftward expansion.

Problem 8: Sliding Window Maximum

LeetCode 239. Find the maximum in every window of size k as the window slides. Sorting each window is $O(nk)$; a monotonic deque is $O(n)$.

The deque stores indices in decreasing order of their values. When the front falls outside the window, pop it. When a new value makes older values useless (smaller values behind a larger new value), pop them from the back.

from collections import deque
from typing import List

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    dq = deque()  # monotonic decreasing deque of indices
    result = []

    for i, num in enumerate(nums):
        # Remove indices outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements — they can never be the max
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))  # [3,3,5,5,6,7]

Trace the first few steps with k=3:
– i=0, val=1: dq=[0]
– i=1, val=3: 3>1, pop 0, dq=[1]
– i=2, val=-1: -1<3, append, dq=[1,2]. Window [0,2] complete → max = nums[1] = 3
– i=3, val=-3: append, dq=[1,2,3]. Window [1,3] → max = nums[1] = 3
– i=4, val=5: 5>-3, pop 3; 5>-1, pop 2; 5>3, pop 1; dq=[4]. Window [2,4] → max = nums[4] = 5

When k equals n, this degenerates to a single maximum query — the deque will contain exactly 1 element at the end. Best case is $O(n)$, worst case is also $O(n)$ because each element is enqueued and dequeued at most once.

Pattern Recognition Cheat Sheet

The “median of stream” pattern (LeetCode 295) deserves its own mention: maintain a max-heap for the lower half and a min-heap for the upper half. After every insertion, enforce two invariants in order: (1) restore the partition invariant — if the max-heap’s top exceeds the min-heap’s top, move the max-heap top to the min-heap; (2) rebalance sizes so they differ by at most 1. The median is either the top of the max-heap (odd total count) or the average of both tops (even count). The rebalancing protocol is specific — enforcing the partition invariant first, then size-balancing, is the correct and reliable approach.

If you’re grinding through problems on a cheap laptop fan-screaming at full throttle, Cooling Pad with USB Hub — getting proper airflow actually helps with focus in long sessions.

FAQ

Q: When should I use heapq.nlargest() vs maintaining a heap manually?
heapq.nlargest(k, iterable) is clean for one-shot queries but internally uses a heap and runs in $O(n \log k)$ — same complexity. Use it for readability when you have all data upfront. If data arrives in a stream (online algorithm), maintain the heap manually so you can insert incrementally.

Q: Why does Python’s heapq not support decrease-key operations like Dijkstra needs?
Python’s heapq doesn’t support update operations at all. The standard workaround is lazy deletion: push a new (priority, item) tuple and mark the old one as stale using a set or dictionary. When you pop, check if the item is stale and skip it. It’s O(log n) per operation but with higher constant factors due to the invalidation check. Libraries like sortedcontainers.SortedList support this natively if you need it.

Q: Is a monotonic stack always O(n)?
Yes, because each element is pushed exactly once and popped at most once, giving a total of 2n operations over the entire array — amortized $O(1)$ per element. The worst-case stack size is still O(n) space (a strictly decreasing input like [5,4,3,2,1] fills the entire stack before anything gets popped).

For interview prep, prioritize in this order: k-th largest (warm-up), sliding window max (tests deque understanding), largest rectangle in histogram (hardest of the group), and merge k sorted lists (tests both heap mechanics and linked list handling). The others are variations you can derive once those four are solid.

For the two-heap median-of-stream (LeetCode 295), practice the rebalancing step as two explicit conditional blocks: first enforce the partition invariant (swap tops if max-heap top > min-heap top), then enforce size balance (move top from larger heap to smaller). Writing it this way makes the logic mechanical and eliminates uncertainty under interview pressure.