Micro-questions over the monotonic stack pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. What problem does it solve, and what does the naive version cost?
Answer
“For each element, find the next greater (or smaller) element.” Naively you scan forward from each position — , so 500,000 comparisons for 1,000 prices.
2. Define a monotonic stack.
Answer
A stack kept strictly increasing or strictly decreasing from bottom to top, by popping anything that would break that order before pushing.
3. What is the stack invariant?
Answer
The order rule the stack maintains — in a monotonic increasing stack, each new element must be larger than the top.
B. The mechanism
4. Describe the loop in one sentence.
Answer
Walk the array once; for each new element, pop everything smaller than it — those elements have just found their next greater element — then push the current index.
5. Why store indices rather than values?
Answer
Because you need to know where to write the answer when you pop, and the index also lets you compute distances (as in Daily Temperatures) and widths (as in Largest Rectangle).
6. Write the next-greater loop.
Answer
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
result[stack.pop()] = num
stack.append(i)7. Trace [2,1,2,4,3].
Answer
i=0 push → [0]. i=1 push → [0,1]. i=2 pop 1 (result[1]=2), push → [0,2]. i=3 pop 2 (result[2]=4), pop 0 (result[0]=4), push → [3]. i=4 push → [3,4].
result = [4, 2, 4, -1, -1].
8. What do the remaining stack entries mean at the end?
Answer
They have no next greater element — which is why the result array is initialised to .
C. Why it is O(n)
9. Give the argument.
Answer
Every index is pushed exactly once and popped at most once across the entire run, so the total push/pop count is bounded by , not .
10. What familiar analysis is that?
Answer
The same amortised argument as dynamic array resizing — the loop looks nested, but total work across the run is linear.
D. Variants
11. How do you find the previous smaller element instead?
Answer
Keep the stack in increasing value order; pop while the top is the current value, then read the answer off the top before pushing:
while stack and nums[stack[-1]] >= num:
stack.pop()
result[i] = stack[-1] if stack else -1
stack.append(i)12. What is the structural difference between the two variants?
Answer
Next-greater writes the answer when it pops; previous-smaller reads the answer when it pushes. One looks forward, the other looks backward.
13. What is a monotonic queue, and what is it for?
Answer
A deque holding indices in decreasing value order — for sliding window maximum, where the aggregate is not invertible.
14. What are its two while loops?
Answer
Pop the front when an index falls out of the window; pop the back while the incoming value is the back’s value — those can never be the maximum again.
E. Trade-offs
15. What kinds of problems does it fit?
Answer
“Next/previous greater/smaller” problems specifically — those with a monotonic condition. Daily Temperatures and Largest Rectangle in Histogram are the classics.
16. How large can the stack get?
Answer
— in the worst case (a strictly increasing array) nothing is ever popped and it contains all indices.
17. What is the key to getting it right?
Answer
Understanding the invariant — which direction the stack is ordered decides both the comparison operator and whether you write on pop or read on push.
18. Summarise the pattern in one sentence.
Answer
Keep a stack in sorted order and let each arriving element evict everything it dominates — each eviction is an answer, and every index is pushed and popped once.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Monotonic Stack — the pattern
- Stacks and Queues — Question Bank
- Sliding Window — Question Bank — where the monotonic deque appears
Software engineering
Infrastructure & security
Computer science
Hardware & engineering