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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes