Heap & Stack Patterns: 8 Interview Problems Solved
TildAliceMost people fail heap problems in interviews not because they don't know what a heap is, but because...
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$$
Continue reading the full article on TildAlice