Why stack vs heap
A stack remembers nested unfinished work (parentheses, path, DFS). A monotonic stack keeps indices in increasing/decreasing order so you can answer ‘next greater’ when you pop. A heap repeatedly gives you the current best item — top-K, merge-K, median with two heaps.
Analogy: ER triage (heap) + plate stack
A stack is a cafeteria plate pile: last on, first off — perfect for nested unfinished work (parentheses, DFS path). A heap is an ER triage board: you always pull the most urgent patient next without sorting everyone by severity every time.
Stack & monotonic stack
def daily_temperatures(t):
ans = [0]*len(t); st = []
for i, x in enumerate(t):
while st and t[st[-1]] < x:
j = st.pop(); ans[j] = i-j
st.append(i)
return ansint[] dailyTemperatures(int[] t) {
int[] ans = new int[t.length];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < t.length; i++) {
while (!st.isEmpty() && t[st.peek()] < t[i]) {
int j = st.pop();
ans[j] = i - j;
}
st.push(i);
}
return ans;
}Heaps
- Top K → size-k heap
- Merge K lists → heap of heads
- Median stream → two heaps
import heapq
def kth_largest(nums, k):
h = []
for x in nums:
heapq.heappush(h, x)
if len(h) > k: heapq.heappop(h)
return h[0]int kthLargest(int[] nums, int k) {
PriorityQueue<Integer> h = new PriorityQueue<>();
for (int x : nums) {
h.offer(x);
if (h.size() > k) h.poll();
}
return h.peek();
}Which tool?
Stack — nested structure, undo, parse. Monotonic stack — next greater/smaller. Heap — repeated ‘best of remaining.’
Worked trace: next warmer day
Temps [73,74,75,71,69,72,76]. Stack holds indices of unresolved days (decreasing temps). At 74, pop 73 and set wait=1. At 76, pop everyone remaining and fill waits. You’re explaining the pops — that’s the insight.
When to reach for this pattern
Stack = LIFO discipline on a line of decisions. Heap = ‘give me the current extreme fast’ under a changing set. Monotonic stack is the interview crossover: you maintain candidates in increasing/decreasing order so the top answers ‘next greater’ in amortized O(1).
Core template + worked trace
Monotonic decreasing stack for next warmer / next greater:
def daily_temperatures(t: list[int]) -> list[int]:
# stack holds indices with decreasing temperatures
ans = [0] * len(t)
stack: list[int] = []
for i, temp in enumerate(t):
while stack and t[stack[-1]] < temp:
j = stack.pop()
ans[j] = i - j # days until warmer
stack.append(i)
return ans
# t=[73,74,75,71,69,72,76,73]
# i=1 (74): pops 0 → ans[0]=1
# i=2 (75): pops 1 → ans[1]=1
# i=5 (72): pops 4,3 → ans[4]=1, ans[3]=2
# i=6 (76): pops 5,2 → ... ans[2]=4int[] dailyTemperatures(int[] t) {
// stack holds indices with decreasing temperatures
int[] ans = new int[t.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < t.length; i++) {
while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
int j = stack.pop();
ans[j] = i - j; // days until warmer
}
stack.push(i);
}
return ans;
}
// t=[73,74,75,71,69,72,76,73]
// i=1 (74): pops 0 → ans[0]=1
// i=2 (75): pops 1 → ans[1]=1
// i=5 (72): pops 4,3 → ans[4]=1, ans[3]=2
// i=6 (76): pops 5,2 → ... ans[2]=4Top-K with a min-heap of size k:
import heapq
def top_k(nums: list[int], k: int) -> list[int]:
heap: list[int] = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop smallest
return heap # k largest, unordered
# nums=[3,1,5,12,2,11], k=3 → heap ends as [5,12,11]List<Integer> topK(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll(); // drop smallest
}
return new ArrayList<>(heap); // k largest, unordered
}
// nums=[3,1,5,12,2,11], k=3 → heap ends as [5,12,11]Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘I’ll keep a decreasing stack of indices. When today’s temperature is warmer than the top, that earlier day just found its answer — pop and write the distance. Each index enters and leaves once, so O(n).’
Practice set
- Valid Parentheses
- Daily Temperatures
- Next Greater Element II
- Largest Rectangle in Histogram
- Kth Largest Element in an Array
- Top K Frequent Elements
- Merge K Sorted Lists
- Find Median from Data Stream
Harder follow-up
Harder variant: Largest Rectangle in Histogram — monotonic increasing stack of indices; when you pop, width spans from the new top+1 to i−1. Same amortized O(n) story.
Pattern bank: more questions + efficient solutions
Five stack/heap staples. Monotonic stacks answer ‘next greater / previous smaller’; heaps answer ‘top-K / merge under order’.
Q: Valid Parentheses — given a string of brackets, return whether every open has a matching close in the correct order.
def is_valid(s):
pair = {')': '(', ']': '[', '}': '{'}
st = []
for ch in s:
if ch in pair:
if not st or st[-1] != pair[ch]:
return False
st.pop()
else:
st.append(ch)
return not st
# O(n) time, O(n) spaceboolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (ch == ')' || ch == ']' || ch == '}') {
if (st.isEmpty()) return false;
char open = st.pop();
if (ch == ')' && open != '(') return false;
if (ch == ']' && open != '[') return false;
if (ch == '}' && open != '{') return false;
} else st.push(ch);
}
return st.isEmpty();
}
// O(n) time, O(n) spaceQ: Daily Temperatures — for each day, how many days until a warmer temperature? 0 if none (monotonic decreasing stack of indices).
def daily_temperatures(temps):
n = len(temps)
ans = [0] * n
st = [] # indices, temps strictly decreasing
for i, t in enumerate(temps):
while st and temps[st[-1]] < t:
j = st.pop()
ans[j] = i - j
st.append(i)
return ans
# O(n) time, O(n) spaceint[] dailyTemperatures(int[] temps) {
int n = temps.length;
int[] ans = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && temps[st.peek()] < temps[i]) {
int j = st.pop();
ans[j] = i - j;
}
st.push(i);
}
return ans;
}
// O(n) time, O(n) spaceQ: Largest Rectangle in Histogram — given bar heights of width 1, find the largest rectangle area in the histogram (monotonic stack).
def largest_rectangle_area(heights):
st = [] # increasing heights indices
best = 0
for i, h in enumerate(heights + [0]):
while st and heights[st[-1]] > h:
height = heights[st.pop()]
left = st[-1] if st else -1
best = max(best, height * (i - left - 1))
st.append(i)
return best
# O(n) time, O(n) spaceint largestRectangleArea(int[] heights) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0, n = heights.length;
for (int i = 0; i <= n; i++) {
int h = i == n ? 0 : heights[i];
while (!st.isEmpty() && heights[st.peek()] > h) {
int height = heights[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
best = Math.max(best, height * (i - left - 1));
}
st.push(i);
}
return best;
}
// O(n) time, O(n) spaceQ: Top K Frequent Elements — return the k most frequent numbers in nums (order among ties flexible unless specified).
from collections import Counter
import heapq
def top_k_frequent(nums, k):
cnt = Counter(nums)
return [x for x, _ in heapq.nlargest(k, cnt.items(), key=lambda kv: kv[1])]
# O(n log k) time, O(n) spaceint[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
for (var e : cnt.entrySet()) {
pq.offer(new int[]{e.getKey(), e.getValue()});
if (pq.size() > k) pq.poll();
}
int[] out = new int[k];
for (int i = k - 1; i >= 0; i--) out[i] = pq.poll()[0];
return out;
}
// O(n log k) time, O(n) spaceQ: Merge K Sorted Lists — merge k sorted linked lists into one sorted list (min-heap on current heads).
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = cur = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(n log k) time, O(k) spaceListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
for (ListNode node : lists) if (node != null) pq.offer(node);
ListNode dummy = new ListNode(0), cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
cur.next = node;
cur = cur.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
// O(n log k) time, O(k) space