# Monotonic Stack: The Pattern Behind "Next Greater Element" Questions If a question asks for the **next greater**, **previous smaller**, or "how many days until a warmer temperature", a monotonic stack usually turns an O(n²) scan into O(n). ## Core idea Keep a stack of indices whose values are in sorted order (decreasing for "next greater"). When a new value breaks the order, it is the answer for every index you pop. ```python def daily_temperatures(temps): # LeetCode 739 ans = [0] * len(temps) stack = [] # indices, temps decreasing for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: j = stack.pop() ans[j] = i - j stack.append(i) return ans ``` Each index is pushed and popped at most once, so the loop is O(n) even with the inner `while`. ## Choosing the direction | Question asks for | Stack keeps values | Pop when new value is | |---|---|---| | Next greater | decreasing | greater | | Next smaller | increasing | smaller | | Previous greater | decreasing | greater or equal (answer = new top) | ## Harder problems that use it - **Largest Rectangle in Histogram (84):** increasing stack; when a bar is popped, its width runs from the new stack top to the current index. - **Trapping Rain Water (42):** popping a lower bar between two taller ones gives the water above it. - **Sum of Subarray Minimums (907):** previous-smaller and next-smaller distances give how many subarrays each element is the minimum of. Handle duplicates with `<` on one side and `<=` on the other. ## How to explain it in the interview Say *why* it is linear: "Every element enters and leaves the stack once." Then trace a 5-element example on the whiteboard; interviewers care more about the invariant than the code. --- *Disclosure: I work on [Linkjob AI's coding interview assistant](https://www.linkjob.ai/coding-interview-copilot/). This write-up is general practice material.*