> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Stack Pattern
> Master LIFO operations for parsing, matching, and monotonic problems
## What is Stack?
**Stack** is a LIFO (Last In, First Out) data structure where elements are added and removed from the same end -- the **top**. Think of it like a spring-loaded plate dispenser in a cafeteria: you can only take the top plate, and when a new plate is added, it goes on top. You never reach into the middle. That constraint -- only the most recent item is accessible -- is exactly what makes stacks powerful for problems that care about *recency* and *nesting*.
In algorithm problems, stacks appear in three major families: **matching problems** (parentheses, tags, nested structures), **expression evaluation** (calculators, compilers), and **monotonic stack problems** (next greater/smaller element, histograms). The key insight is always the same: when the "most recently seen" item determines what happens next, a stack is the right tool.
**Key operations and their complexity:**
* `push` (add to top): O(1)
* `pop` (remove from top): O(1)
* `peek/top` (view top without removing): O(1)
**Common pitfall in practice:** In Python, `list` works perfectly as a stack (`append` and `pop` are both O(1)). But in Java, prefer `ArrayDeque` over `Stack` -- the `Stack` class is synchronized and inherits from `Vector`, adding unnecessary overhead. The Java docs themselves recommend `Deque` as a replacement.
**Quick Recognition**: Problems involving matching pairs, nested structures, "previous/next greater element", or undo operations. If you need to track "the most recent unresolved thing," reach for a stack.
## Pattern Recognition Cheatsheet
**These exact problem-statement keywords should make you reach for a stack within 30 seconds of reading.** Build the mental reflex once and you will solve most stack problems before the interviewer finishes explaining them.
| Keyword / Shape in Problem | Stack Variant to Use |
| ------------------------------------------------------------- | --------------------------------------------- |
| "matching parens", "balanced brackets", "valid HTML/XML tags" | Push openers, pop on closer, match types |
| "next greater element", "next smaller", "first warmer day" | Monotonic stack of indices |
| "evaluate expression", "calculator", "RPN", "infix" | Operand stack (or two stacks for operators) |
| "decode string", "nested encoding", "k\[ab]" | Stack of (prev\_string, repeat\_count) tuples |
| "undo / redo", "browser back", "history" | Two stacks (action plus inverse) |
| "simplify path", "canonical path", "/.. /." | Push directories, pop on `..` |
| "asteroid collision", "remove adjacent duplicates" | Push, pop on collision rule |
| "min stack" / "max stack" with O(1) query | Auxiliary stack of running min or max |
| "largest rectangle in histogram", "trap rain water" | Monotonic increasing or decreasing stack |
| "stock span", "previous greater day" | Monotonic decreasing stack of (price, span) |
| "the most recent X that..." | Plain LIFO stack of candidates |
**Rule of thumb:** if the problem talks about *recency* ("most recent unresolved...") or *nesting* ("inside the inner..."), it is a stack. If it talks about *order of arrival* ("first one in...") it is a queue. If it talks about *the next/previous element with property P*, it is a monotonic stack.
## Reusable Template Code
Three skeletons cover the vast majority of stack problems. Internalize them and you will write each one in under a minute under interview pressure.
```python Python theme={null}
# Skeleton 1: Matching / balanced brackets
def matching_brackets(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in pairs.values(): # opener
stack.append(c)
elif c in pairs: # closer
if not stack or stack.pop() != pairs[c]:
return False
return not stack # all openers must be closed
# Skeleton 2: Monotonic stack (next greater / smaller)
def monotonic_next_greater(nums):
result = [-1] * len(nums)
stack = [] # stores INDICES, not values
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
result[stack.pop()] = x # pop's "next greater" is current
stack.append(i)
return result
# Skeleton 3: Save-and-restore context (Calculator, Decode String)
def context_stack(s):
stack = []
state = initial_state()
for c in s:
if opens_new_context(c):
stack.append(state) # snapshot outer context
state = initial_state() # reset for inner work
elif closes_context(c):
outer = stack.pop()
state = combine(outer, state) # merge inner result into outer
else:
state = update(state, c)
return state
```
```java Java theme={null}
// Skeleton 1: Matching brackets
public boolean matchingBrackets(String s) {
Deque stack = new ArrayDeque<>(); // ArrayDeque, NOT Stack class
Map pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) stack.push(c);
else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
// Skeleton 2: Monotonic stack
public int[] nextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
```
**Java specific:** never use `java.util.Stack`. It extends `Vector` and is synchronized -- meaning every `push` and `pop` takes a lock you do not need. Use `Deque` with `ArrayDeque<>()` as the implementation. The Java docs themselves recommend this. The `Stack` class exists only for legacy compatibility.
## Pattern Recognition Checklist
* Matching parentheses/brackets/tags
* Evaluating expressions (postfix/infix)
* Finding next/previous greater/smaller
* Processing nested structures
* Implementing undo/back operations
* Need random access to elements
* FIFO ordering needed (use Queue)
* Need to process from both ends
* Simple array traversal suffices
## Stack Type Quick Reference
| Problem Type | Stack Type | Direction |
| ------------------------ | -------------------- | -------------------- |
| Next Greater Element | Monotonic Decreasing | Left to Right |
| Previous Greater Element | Monotonic Decreasing | Left to Right |
| Next Smaller Element | Monotonic Increasing | Left to Right |
| Largest Rectangle | Monotonic Increasing | Left to Right |
| Trapping Rain Water | Either | Two-pointer or stack |
## When to Use
Parentheses, tags, nested structures
Infix, postfix, prefix expressions
Next greater/smaller element
Browser history, text editors
## Pattern Variations
### 1. Valid Parentheses
The classic stack problem. The core insight: **the most recently opened bracket must be the first one closed**. That is exactly LIFO ordering. A counter alone cannot solve this for multiple bracket types -- `([)]` has balanced counts but invalid nesting. Only a stack tracks the *order* of opens.
**Complexity:** O(n) time, O(n) space in the worst case (all opening brackets).
**Edge cases:** Empty string (valid), single character (always invalid), only opening brackets (stack leftover -- invalid), only closing brackets (empty stack check catches it).
```python Python theme={null}
def is_valid(s):
"""Check if parentheses are balanced and properly nested.
Walkthrough with '({[]})':
char='(' -> push '('. stack=['(']
char='{' -> push '{'. stack=['(', '{']
char='[' -> push '['. stack=['(', '{', '[']
char=']' -> top='[' matches. stack=['(', '{']
char='}' -> top='{' matches. stack=['(']
char=')' -> top='(' matches. stack=[]
Stack empty -> valid!
"""
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping: # Closing bracket
if not stack or stack[-1] != mapping[char]:
return False # Mismatch or no matching opener
stack.pop()
else: # Opening bracket
stack.append(char)
return len(stack) == 0 # Leftover openers = invalid
```
```java Java theme={null}
public boolean isValid(String s) {
// Check if parentheses are balanced and properly nested
Stack stack = new Stack<>();
Map mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put('}', '{');
mapping.put(']', '[');
for (char c : s.toCharArray()) {
if (mapping.containsKey(c)) { // Closing bracket
if (stack.isEmpty() || stack.peek() != mapping.get(c)) {
return false;
}
stack.pop();
} else { // Opening bracket
stack.push(c);
}
}
return stack.isEmpty();
}
```
```cpp C++ theme={null}
bool isValid(string s) {
// Check if parentheses are balanced and properly nested
stack stk;
unordered_map mapping = {
{')', '('},
{'}', '{'},
{']', '['}
};
for (char c : s) {
if (mapping.count(c)) { // Closing bracket
if (stk.empty() || stk.top() != mapping[c]) {
return false;
}
stk.pop();
} else { // Opening bracket
stk.push(c);
}
}
return stk.empty();
}
```
### 2. Decode String
This problem extends the matching pattern by storing *context* (the accumulated string and its repeat count) on the stack. Think of it like nested function calls: each `[` opens a new scope with its own local variables. On `]`, you return the result to the caller scope.
**Complexity:** O(output\_length) time -- the output can be exponentially larger than the input (e.g., `10[10[10[a]]]` produces 1000 characters from \~15 input characters).
**Edge case:** Multi-digit numbers like `12[a]` -- you must build the number digit by digit with `current_num = current_num * 10 + int(char)`.
```python Python theme={null}
def decode_string(s):
"""Decode strings like '3[a2[c]]' -> 'accaccacc'
Walkthrough with '3[a2[c]]':
'3' -> current_num = 3
'[' -> push ("", 3), reset: current_str="", current_num=0
'a' -> current_str = "a"
'2' -> current_num = 2
'[' -> push ("a", 2), reset: current_str="", current_num=0
'c' -> current_str = "c"
']' -> pop ("a", 2): current_str = "a" + "c"*2 = "acc"
']' -> pop ("", 3): current_str = "" + "acc"*3 = "accaccacc"
"""
stack = []
current_num = 0
current_str = ""
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append((current_str, current_num))
current_str = ""
current_num = 0
elif char == ']':
prev_str, num = stack.pop()
current_str = prev_str + current_str * num
else:
current_str += char
return current_str
```
```java Java theme={null}
public String decodeString(String s) {
// Decode strings like '3[a2[c]]' -> 'accaccacc'
Stack strStack = new Stack<>();
Stack numStack = new Stack<>();
StringBuilder current = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
strStack.push(current.toString());
numStack.push(num);
current = new StringBuilder();
num = 0;
} else if (c == ']') {
String prev = strStack.pop();
int repeat = numStack.pop();
StringBuilder temp = new StringBuilder(prev);
for (int i = 0; i < repeat; i++) {
temp.append(current);
}
current = temp;
} else {
current.append(c);
}
}
return current.toString();
}
```
```cpp C++ theme={null}
string decodeString(string s) {
// Decode strings like '3[a2[c]]' -> 'accaccacc'
stack strStack;
stack numStack;
string current = "";
int num = 0;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
strStack.push(current);
numStack.push(num);
current = "";
num = 0;
} else if (c == ']') {
string prev = strStack.top(); strStack.pop();
int repeat = numStack.top(); numStack.pop();
string temp = prev;
for (int i = 0; i < repeat; i++) {
temp += current;
}
current = temp;
} else {
current += c;
}
}
return current;
}
```
### 3. Basic Calculator
The stack acts as a **context saver** here. On `(`, you pause the outer evaluation by pushing the running result and current sign, then start fresh inside the parentheses. On `)`, you merge the inner result back into the outer context. This is exactly how call stacks work in programming languages -- every function call saves the caller's state, and every return restores it.
**Complexity:** O(n) time, O(d) space where d is the maximum nesting depth.
**Edge cases:** Leading minus sign (e.g., `"-1+2"`), spaces between characters, deeply nested expressions like `((((1+2))))`.
```python Python theme={null}
def calculate(s):
"""Evaluate expression with +, -, (, ).
Walkthrough with '1 - (2 + 3)':
'1' -> number=1
'-' -> result=1, sign=-1, number=0
'(' -> push (1, -1), result=0, sign=1
'2' -> number=2
'+' -> result=2, sign=1, number=0
'3' -> number=3
')' -> result=2+1*3=5. Pop: result = 5*(-1) + 1 = -4
Result: -4
"""
stack = []
result = 0
number = 0
sign = 1
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == '+':
result += sign * number
number = 0
sign = 1
elif char == '-':
result += sign * number
number = 0
sign = -1
elif char == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
result += sign * number
number = 0
result *= stack.pop() # sign
result += stack.pop() # previous result
return result + sign * number
```
```java Java theme={null}
public int calculate(String s) {
// Evaluate expression with +, -, (, )
Stack stack = new Stack<>();
int result = 0;
int number = 0;
int sign = 1;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '+') {
result += sign * number;
number = 0;
sign = 1;
} else if (c == '-') {
result += sign * number;
number = 0;
sign = -1;
} else if (c == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * number;
number = 0;
result *= stack.pop(); // sign
result += stack.pop(); // previous result
}
}
return result + sign * number;
}
```
```cpp C++ theme={null}
int calculate(string s) {
// Evaluate expression with +, -, (, )
stack stk;
int result = 0;
int number = 0;
int sign = 1;
for (char c : s) {
if (isdigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '+') {
result += sign * number;
number = 0;
sign = 1;
} else if (c == '-') {
result += sign * number;
number = 0;
sign = -1;
} else if (c == '(') {
stk.push(result);
stk.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * number;
number = 0;
result *= stk.top(); stk.pop(); // sign
result += stk.top(); stk.pop(); // previous result
}
}
return result + sign * number;
}
```
### 4. Min Stack
The key insight: a single stack cannot give O(1) minimum because popping might change the min, and you would need to scan. The fix is a **second "min stack"** that mirrors the main stack's minimum at every height. The space-time trade-off is the core of this problem.
**Critical detail:** Push to the min stack when `val <= min_stack[-1]`, NOT when `val < min_stack[-1]`. The `<=` handles duplicate minimums. Without it, popping one copy of the minimum incorrectly removes it from the min stack while another copy still exists on the main stack.
**Complexity:** O(1) for all operations. O(n) extra space in the worst case (strictly decreasing input fills both stacks equally).
```python Python theme={null}
class MinStack:
"""Stack that supports O(1) getMin().
Example sequence:
push(3) -> stack=[3], min_stack=[3]
push(1) -> stack=[3,1], min_stack=[3,1] (1 <= 3)
push(1) -> stack=[3,1,1], min_stack=[3,1,1] (1 <= 1, crucial!)
pop() -> stack=[3,1], min_stack=[3,1] (popped 1 == min top 1)
getMin() -> 1 (correct! would be wrong with < instead of <=)
"""
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
```
```java Java theme={null}
class MinStack {
// Stack that supports O(1) getMin()
private Stack stack;
private Stack minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
```
```cpp C++ theme={null}
class MinStack {
// Stack that supports O(1) getMin()
private:
stack stk;
stack minStk;
public:
MinStack() {}
void push(int val) {
stk.push(val);
if (minStk.empty() || val <= minStk.top()) {
minStk.push(val);
}
}
void pop() {
if (stk.top() == minStk.top()) {
minStk.pop();
}
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return minStk.top();
}
};
```
### 5. Daily Temperatures (Monotonic Stack)
A direct application of the "next greater element" pattern. The stack holds indices of days still "waiting" for a warmer day. When a warmer day arrives, it resolves all waiting days that are cooler -- each popped element records the distance (index difference) to the warmer day. Think of the stack as a waiting room: days sit there until someone warmer shows up, then they leave and never come back.
**Complexity:** O(n) time (each element is pushed and popped at most once -- amortized O(1) per element). O(n) space for the stack.
**Interview tip:** Always store **indices** on the stack, not values. You need the index for the distance calculation (`i - idx`), and you can always look up the value via `temperatures[idx]`.
```python Python theme={null}
def daily_temperatures(temperatures):
"""Days until warmer temperature for each day.
Walkthrough with [73, 74, 75, 71, 69, 72, 76, 73]:
i=0: stack=[] -> push 0. stack=[0]
i=1: 74>73 -> pop 0, result[0]=1-0=1. stack=[1]
i=2: 75>74 -> pop 1, result[1]=2-1=1. stack=[2]
i=3: 71<75 -> push 3. stack=[2,3]
i=4: 69<71 -> push 4. stack=[2,3,4]
i=5: 72>69,72>71 -> pop 4(5-4=1), pop 3(5-3=2). stack=[2,5]
i=6: 76>72,76>75 -> pop 5(6-5=1), pop 2(6-2=4). stack=[6]
i=7: 73<76 -> push 7. stack=[6,7]
Remaining in stack -> result stays 0.
Result: [1, 1, 4, 2, 1, 1, 0, 0]
"""
n = len(temperatures)
result = [0] * n
stack = [] # indices of temperatures waiting for warmer day
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
stack.append(i)
return result
```
```java Java theme={null}
public int[] dailyTemperatures(int[] temperatures) {
// Days until warmer temperature for each day
int n = temperatures.length;
int[] result = new int[n];
Stack stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prevIdx = stack.pop();
result[prevIdx] = i - prevIdx;
}
stack.push(i);
}
return result;
}
```
```cpp C++ theme={null}
vector dailyTemperatures(vector& temperatures) {
// Days until warmer temperature for each day
int n = temperatures.size();
vector result(n, 0);
stack stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
int prevIdx = stk.top();
stk.pop();
result[prevIdx] = i - prevIdx;
}
stk.push(i);
}
return result;
}
```
## Classic Problems
**Pattern**: Push opening, pop and match closing
**Key**: Stack should be empty at end for valid input
**Pattern**: Monotonic increasing stack
**Key**: Pop and calculate area when current bar is shorter
**Pattern**: Push numbers, pop two on operator
**Key**: Order matters for subtraction/division
**Pattern**: Split by '/', stack for directory navigation
**Key**: '..' pops, '.' and '' are ignored
## Monotonic Stack Deep Dive
The monotonic stack is one of the most powerful -- and most misunderstood -- patterns. The core principle: **maintain elements on the stack in sorted order, and extract answers at the moment you pop**. Every element is pushed exactly once and popped at most once, giving O(n) amortized time even though the code has a while-loop inside a for-loop.
**Decision guide:** Use a monotonic *decreasing* stack when searching for the "next greater" element. Use a monotonic *increasing* stack when searching for the "next smaller" element or computing areas in histograms. The rule: the stack direction is *opposite* to what you are searching for.
```python Python theme={null}
def next_greater_element(nums):
"""For each element, find the first element to its right that is larger.
Return -1 if no such element exists.
Walkthrough with [4, 2, 1, 3, 5]:
i=0: stack=[] -> push 0. stack=[0]
i=1: 2<4 -> push 1. stack=[0,1]
i=2: 1<2 -> push 2. stack=[0,1,2]
i=3: 3>1 -> pop 2, result[2]=3. stack=[0,1]
3>2 -> pop 1, result[1]=3. stack=[0]
3<4 -> push 3. stack=[0,3]
i=4: 5>3 -> pop 3, result[3]=5. stack=[0]
5>4 -> pop 0, result[0]=5. stack=[]
push 4. stack=[4]
Remaining -> result[4]=-1.
Result: [5, 3, 3, 5, -1]
"""
result = [-1] * len(nums)
stack = [] # Indices of elements waiting for their next greater
for i in range(len(nums)):
# Pop all elements smaller than current -- they just found their answer
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i] # Current element is the "next greater"
stack.append(i)
# Anything still on the stack has no next greater element (stays -1)
return result
def largest_rectangle_histogram(heights):
"""Find largest rectangle in histogram.
Key insight: for each bar, find how far left and right it can extend
as the shortest bar. A sentinel value (0) appended at the end forces
all remaining bars to be popped, eliminating the need for cleanup code.
Walkthrough with [2, 1, 5, 6, 2, 3]:
After appending sentinel: [2, 1, 5, 6, 2, 3, 0]
i=0: push 0. stack=[0]
i=1: 1<2 -> pop 0: h=2, w=1 (empty stack), area=2. stack=[1]
i=2: push 2. stack=[1,2]
i=3: push 3. stack=[1,2,3]
i=4: 2<6 -> pop 3: h=6, w=4-2-1=1, area=6. stack=[1,2]
2<5 -> pop 2: h=5, w=4-1-1=2, area=10. stack=[1]
push 4. stack=[1,4]
i=5: push 5. stack=[1,4,5]
i=6: 0<3 -> pop 5: h=3, w=6-4-1=1, area=3. stack=[1,4]
0<2 -> pop 4: h=2, w=6-1-1=4, area=8. stack=[1]
0<1 -> pop 1: h=1, w=6 (empty), area=6. stack=[]
max_area = 10 (height=5, spanning indices 2-3)
"""
stack = [] # Monotonic increasing stack of indices
max_area = 0
heights.append(0) # Sentinel forces all bars to pop at the end
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# Width: everything between new top and current index was taller
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
```
```java Java theme={null}
public int[] nextGreaterElement(int[] nums) {
// For each element, find next greater element or -1
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Stack stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}
public int largestRectangleHistogram(int[] heights) {
// Find largest rectangle in histogram
Stack stack = new Stack<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
```
```cpp C++ theme={null}
vector nextGreaterElement(vector& nums) {
// For each element, find next greater element or -1
vector result(nums.size(), -1);
stack stk;
for (int i = 0; i < nums.size(); i++) {
while (!stk.empty() && nums[i] > nums[stk.top()]) {
int idx = stk.top();
stk.pop();
result[idx] = nums[i];
}
stk.push(i);
}
return result;
}
int largestRectangleHistogram(vector& heights) {
// Find largest rectangle in histogram
stack stk;
int maxArea = 0;
heights.push_back(0); // Sentinel
for (int i = 0; i < heights.size(); i++) {
while (!stk.empty() && heights[stk.top()] > heights[i]) {
int height = heights[stk.top()];
stk.pop();
int width = stk.empty() ? i : i - stk.top() - 1;
maxArea = max(maxArea, height * width);
}
stk.push(i);
}
return maxArea;
}
```
## Worked LeetCode Problems: Brute Force vs Optimized
Five canonical problems cover the entire stack interview surface. For each, name the brute force first, then pivot to the stack solution. Interviewers love hearing the trade-off out loud.
### LC 20: Valid Parentheses (Easy)
**Problem.** Given a string containing only `()[]{}`, determine if it is valid -- every opener has a matching closer in the right order.
**Brute force (O(n^2)).** Repeatedly scan and remove inner matched pairs (`()`, `[]`, `{}`) until nothing changes. Slow and ugly.
**Optimized stack (O(n) time, O(n) space).** Push openers; on a closer, the stack top must be the matching opener. Empty stack at the end means valid.
```python theme={null}
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack or stack.pop() != pairs[c]:
return False
return not stack
```
**Why a stack and not a counter?** A counter passes balanced-but-misnested cases like `([)]`. Only a stack tracks the *order* of opens.
### LC 155: Min Stack (Medium)
**Problem.** Design a stack that supports `push`, `pop`, `top`, and `getMin`, all in O(1).
**Brute force.** Scan the whole stack on `getMin` -- O(n) per call. Fails the constraint.
**Optimized -- auxiliary min stack.** Maintain a parallel stack whose top is always the current minimum. Push to the aux stack only when the new value is `<=` the current min (the `<=` is critical for handling duplicate minimums).
```python theme={null}
class MinStack:
def __init__(self):
self.s, self.mins = [], []
def push(self, x):
self.s.append(x)
if not self.mins or x <= self.mins[-1]: # <= handles duplicate min
self.mins.append(x)
def pop(self):
if self.s.pop() == self.mins[-1]:
self.mins.pop()
def top(self): return self.s[-1]
def getMin(self): return self.mins[-1]
```
**The `<=` trap.** With strict `<`, pushing `[2, 0, 0]` and popping the first `0` removes it from the min stack. Now `getMin()` returns `2` even though a `0` is still on the main stack. The interviewer is testing whether you spot this.
### LC 224: Basic Calculator (Hard)
**Problem.** Evaluate an expression containing `+`, `-`, `(`, `)` and integers.
**Brute force.** Convert infix to RPN with shunting-yard, then evaluate. Works but is overkill for `+/-/()`.
**Optimized -- one stack tracking running result and sign.** On `(`, snapshot the current `result` and `sign` onto the stack and reset; on `)`, pop them and merge the inner result into the outer context.
```python theme={null}
def calculate(s):
stack = []
result = num = 0
sign = 1
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in '+-':
result += sign * num
num = 0
sign = 1 if c == '+' else -1
elif c == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif c == ')':
result += sign * num
num = 0
result *= stack.pop() # saved sign
result += stack.pop() # saved outer result
return result + sign * num
```
**The push-two-things insight.** Most candidates push only the result and forget the sign. Then `1 - (2 + 3)` returns the wrong answer because the outer minus is lost. Push BOTH.
### LC 71: Simplify Path (Medium)
**Problem.** Given a Unix-style absolute path, return the canonical form.
**Brute force.** String manipulation with regex -- error-prone and brittle for edge cases like `///` or `/...`
**Optimized stack.** Split by `/`. For each component: ignore `.` and empty strings; pop on `..`; push otherwise. Join with `/`.
```python theme={null}
def simplify_path(path):
stack = []
for part in path.split('/'):
if part == '..':
if stack: stack.pop()
elif part and part != '.':
stack.append(part)
return '/' + '/'.join(stack)
```
**Edge case test.** `/../` should return `/`. `/home//foo/` should return `/home/foo`. `/...` should return `/...` (a literal directory named `...`).
### LC 739: Daily Temperatures (Medium) -- Bridge to Monotonic Stack
**Problem.** For each day, return how many days until a warmer temperature.
**Brute force (O(n^2)).** For each day, scan forward until warmer.
**Optimized monotonic stack (O(n)).** Stack holds *indices* of days waiting for a warmer day. When today is warmer than the day on top, pop and record `today - popped_index`.
```python theme={null}
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # indices of waiting days
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result # remaining indices keep result 0
```
**Why O(n) despite the inner loop?** Each index is pushed once and popped at most once -- 2n operations max across the whole traversal. This is the amortized argument every interviewer asks about.
## Common Mistakes
**Caveats and Traps -- The Bugs Every Stack Problem Hides:**
1. **Popping an empty stack throws.** Python `IndexError`, Java `EmptyStackException`/`NoSuchElementException`. Always guard with `if stack:` (Python), `!stack.isEmpty()` (Java), or `!stk.empty()` (C++) before every `peek` and `pop`.
2. **Expression evaluation: precedence is not free.** Naive single-stack evaluation works for `+/-/()` but breaks on `*//` because of operator precedence. Use two stacks (operands + operators) or convert to RPN with the shunting-yard algorithm.
3. **String immutability in Java means you cannot just "pop a char" off a `String`.** Use `StringBuilder` and call `deleteCharAt(length-1)`, or maintain an actual `Deque`. Concatenating with `s = s.substring(0, s.length()-1)` is O(n) per pop, turning your O(n) algorithm into O(n^2).
4. **Wrong monotonic direction.** Increasing stack finds *next smaller*; decreasing stack finds *next greater*. Get the direction backward and the algorithm computes the opposite of what you want -- and the bug is invisible until you trace a small example.
5. **Storing values instead of indices.** Without indices, you cannot compute distances (Daily Temperatures), widths (Largest Rectangle), or write results back to the correct position.
6. **Forgetting elements left on the stack at the end.** In "next greater", remaining elements have no answer (set to -1). In "largest rectangle", remaining bars still have areas to compute. Use a sentinel value (append `0`) to force a clean flush, or process the stack after the loop.
7. **Off-by-one in monotonic stack widths.** The width on pop is `i - stack[-1] - 1`, NOT `i - popped_index`. Get this wrong and Largest Rectangle is silently incorrect.
**Solutions and Idioms -- Paired with the Caveats Above:**
1. **Defensive guard:** make `if stack and ...` your reflex on every while-loop condition. The Python `and` short-circuits, so the empty check costs nothing.
2. **For mixed precedence:** use two stacks -- one for numbers, one for operators -- and pop-and-apply when you see an operator of equal or higher precedence than the new one. This is shunting-yard's heart in three lines.
3. **Java string popping:** use `StringBuilder sb` and `sb.deleteCharAt(sb.length() - 1)` -- O(1) amortized. Or model the string as `Deque` directly.
4. **Monotonic direction mantra:** say "I want next *greater*, so I keep a *decreasing* stack -- when something larger arrives, it pops smaller waiters." Reverse the words for "next smaller". Speak it before you code.
5. **Default to indices:** push `i`, not `nums[i]`. Recover the value via `nums[stack[-1]]` whenever you need it. Costs nothing, gains everything.
6. **Sentinel trick:** append a dummy minimum value (`heights.append(0)` for histogram, `temperatures.append(float('inf'))` for daily temps) to force the final flush, eliminating the post-loop cleanup.
7. **Width incantation:** "Width is current index minus new top minus one, because the new top is exclusive on the left and the current index is exclusive on the right." Repeat until reflexive.
## Curated LeetCode Practice List
The classic stack problem set, grouped by difficulty. Solve them in order within each tier.
### Easy
| # | Problem | Pattern Variant |
| ---- | --------------------------------------------------------------------------------------------------------- | ---------------------- |
| 20 | [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) | Bracket matching |
| 232 | [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) | Two-stack amortization |
| 225 | [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) | Reverse trick |
| 1047 | [Remove All Adjacent Duplicates](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/) | Push-or-cancel |
| 844 | [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/) | Stack simulation |
| 682 | [Baseball Game](https://leetcode.com/problems/baseball-game/) | Direct stack ops |
### Medium
| # | Problem | Pattern Variant |
| --- | --------------------------------------------------------------------------------- | ---------------------------- |
| 155 | [Min Stack](https://leetcode.com/problems/min-stack/) | Auxiliary stack for O(1) min |
| 150 | [Evaluate RPN](https://leetcode.com/problems/evaluate-reverse-polish-notation/) | Operand stack |
| 71 | [Simplify Path](https://leetcode.com/problems/simplify-path/) | Path component stack |
| 394 | [Decode String](https://leetcode.com/problems/decode-string/) | Save-restore context |
| 739 | [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) | Monotonic decreasing |
| 503 | [Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/) | Circular monotonic |
| 735 | [Asteroid Collision](https://leetcode.com/problems/asteroid-collision/) | Conditional pop on collision |
| 901 | [Online Stock Span](https://leetcode.com/problems/online-stock-span/) | Streaming monotonic |
### Hard
| # | Problem | Pattern Variant |
| --- | ----------------------------------------------------------------------------------------------- | -------------------------- |
| 84 | [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) | Monotonic increasing |
| 85 | [Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/) | Per-row histogram |
| 224 | [Basic Calculator](https://leetcode.com/problems/basic-calculator/) | Save-restore context |
| 772 | [Basic Calculator III](https://leetcode.com/problems/basic-calculator-iii/) | Two stacks plus precedence |
| 42 | [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/) | Monotonic decreasing |
## Common Mistakes
**Avoid These Pitfalls:**
1. **Empty stack access**: Always check if stack is empty before peek/pop
2. **Forgetting to process remaining**: Stack may still have elements after loop
3. **Wrong monotonic direction**: Know when to use increasing vs decreasing stack
4. **Not storing indices**: Often need index for distance calculations
## Debugging Checklist
Always verify `!stack.empty()` before `peek()` or `pop()`
For parentheses: opening pushes, closing pops and compares
After loop, stack may still have unprocessed elements
Increasing: pop smaller, Decreasing: pop larger
For distance calculations, store indices not values
## Interview Problems by Company
| Problem | Company | Key Concept |
| ------------------- | --------- | -------------------- |
| Valid Parentheses | All FAANG | Push open, pop close |
| Baseball Game | Amazon | Stack operations |
| Remove Outer Parens | Google | Counter or stack |
| Backspace String | Google | Stack simulation |
| Problem | Company | Key Concept |
| ------------------ | ----------------- | ----------------- |
| Min Stack | Amazon, Bloomberg | Two stacks |
| Daily Temperatures | Meta, Amazon | Monotonic stack |
| Decode String | Google, Meta | Nested processing |
| Asteroid Collision | Amazon | Simulation |
| Evaluate RPN | Amazon | Operand stack |
| Problem | Company | Key Concept |
| ------------------- | ------------ | -------------------- |
| Largest Rectangle | All FAANG | Monotonic increasing |
| Basic Calculator | Meta, Google | Two stacks |
| Maximal Rectangle | Google | DP + monotonic |
| Trapping Rain Water | All FAANG | Stack or two-pointer |
## Interview Tips
**Script for interviews:**
1. "This is a matching problem, so I'll use a stack."
2. "Opening brackets push, closing brackets pop and compare."
3. "If match fails or stack has leftovers, it's invalid."
4. "For monotonic: I maintain a stack where elements are always sorted."
| Interviewer Says | You Should Think |
| ---------------------------- | ------------------------------- |
| "Valid parentheses/brackets" | Basic stack push/pop |
| "Next greater element" | Monotonic decreasing stack |
| "Largest rectangle" | Monotonic increasing stack |
| "Evaluate expression" | Two stacks (operand + operator) |
| "Simplify path" | Stack for directory navigation |
```python theme={null}
def next_greater(arr):
result = [-1] * len(arr)
stack = [] # stores indices
for i in range(len(arr)):
# Pop while current is greater than stack top
while stack and arr[i] > arr[stack[-1]]:
idx = stack.pop()
result[idx] = arr[i]
stack.append(i)
return result
```
## Practice Problems
| Problem | Difficulty | Link |
| ------------------------------ | ---------- | ---------------------------------------------------------------------------- |
| Valid Parentheses | Easy | [LeetCode 20](https://leetcode.com/problems/valid-parentheses/) |
| Min Stack | Medium | [LeetCode 155](https://leetcode.com/problems/min-stack/) |
| Daily Temperatures | Medium | [LeetCode 739](https://leetcode.com/problems/daily-temperatures/) |
| Largest Rectangle in Histogram | Hard | [LeetCode 84](https://leetcode.com/problems/largest-rectangle-in-histogram/) |
| Basic Calculator | Hard | [LeetCode 224](https://leetcode.com/problems/basic-calculator/) |
## Practice Roadmap
* Solve: Valid Parentheses, Min Stack
* Focus: Push, pop, peek operations
* Solve: Evaluate RPN, Decode String
* Focus: Operand vs operator stacks
* Solve: Next Greater Element, Daily Temperatures
* Focus: When to pop from stack
* Solve: Largest Rectangle, Basic Calculator
* Focus: Complex monotonic patterns
**Interview Tip**: When you need to track "previous" or "next" elements with certain properties, think Monotonic Stack. When you see nested structures that must be resolved inside-out, think basic stack. Before coding any stack solution, ask yourself three things: (1) what goes on the stack (values or indices?), (2) when do I pop (what triggers resolution?), and (3) what do I do with remaining elements after the loop?
## Interview Questions
Deep-dive questions that test real understanding of the Stack pattern, not just whether you can push and pop. Expect interviewers to keep digging past your first answer.
**Difficulty:** Foundational
**What interviewers are really testing:** Whether you understand *why* LIFO ordering is the correct invariant for matching nested structures, not just that "you use a stack for parentheses." A candidate who can articulate the nesting argument can generalize to HTML tags, XML parsers, and compiler front-ends.
**Strong answer:**
* The key insight is that **the most recently opened bracket must be the first one closed**. That is exactly the LIFO property. If I see `({[`, the `[` must close before the `{`, which must close before the `(`. A stack naturally enforces this ordering.
* **Algorithm:** Iterate through the string. Push every opening bracket. On a closing bracket, check that the stack is not empty AND the top matches. Pop on match, return false on mismatch. At the end, the stack must be empty -- leftover openers mean unclosed brackets.
* **Why not a counter?** A single counter works for one bracket type (just track `open - close >= 0`), but with multiple types it fails. `([)]` has balanced counts but is invalid because the nesting order is wrong. Only a stack tracks the *order* of opens.
* **Real-world connection:** This exact algorithm is the first pass of every compiler's lexer and every JSON/XML parser. VS Code's bracket matching uses this logic on every keystroke.
```python theme={null}
# The mapping trick: store closing -> opening for O(1) lookup
mapping = {`)`: `(`, `}`: `{`, `]`: `[`}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
```
**Red flag answer:** "I would use a counter for each bracket type and check they all end at zero." This misses that `([)]` is invalid despite balanced counts. Another red flag: not checking for empty stack before peeking -- this is the #1 runtime error in stack problems.
**Follow-ups:**
1. What if the string contains non-bracket characters (like `a * (b + c) - {d}`}? How does your solution change? (Answer: simply skip characters not in the mapping or the opener set. The algorithm is identical otherwise.)
2. What if I ask you to return the *index* of the first mismatched bracket instead of just true/false? How does your approach adapt? (Answer: track indices alongside characters on the stack. On mismatch, you have the index immediately. On leftover openers, the bottom of the stack gives the earliest unclosed index.)
**Difficulty:** Intermediate
**What interviewers are really testing:** Whether you can identify the **space-time trade-off** at the heart of this design. O(1) min retrieval is only possible by trading space. This also tests whether you handle edge cases like duplicate minimums correctly -- a subtle bug that trips up most candidates.
**Strong answer:**
* The core insight: a single stack cannot give O(1) minimum because removing an element might change the minimum, and you would need to scan. The fix is a **second stack (the min stack)** that mirrors the main stack's minimum at every height.
* **Push:** Push to main stack. Push to min stack if the value is `<=` the current min (or if min stack is empty). The `<=` is critical -- not `<`. If I push `[2, 0, 0]` and use `<`, the min stack only has `[2, 0]`. When I pop the first `0`, the min stack pops its `0`, and now `getMin()` returns `2` even though a `0` is still on the main stack.
* **Pop:** Pop from main stack. If the popped value equals the min stack's top, pop the min stack too.
* **Alternative approach:** Instead of a separate min stack, store `(value, current_min)` tuples on a single stack. Same O(n) space, slightly simpler logic, but doubles the memory per element.
* **Space analysis:** Worst case (strictly decreasing input), the min stack is the same size as the main stack -- O(n). Best case (strictly increasing input), the min stack has only one element. Average case depends on the distribution.
```python theme={null}
# The <= trap -- this MUST be <= not <
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val) # <= handles duplicates
```
**Red flag answer:** "Use a variable to track the minimum." This breaks on pop -- how do you know the new minimum? You would need to scan the entire stack, making pop O(n). Another red flag: using `<` instead of `<=` for the min stack push condition and not catching the duplicate minimum bug.
**Follow-ups:**
1. Can you implement MinStack using O(1) *extra* space (not O(n))? Hint: store something other than the raw value. (Answer: store the difference between the value and the current min. When the stored value is negative, it means we pushed a new minimum. On pop, use the difference to recover the previous min. This is clever but fragile with integer overflow.)
2. What if I also need O(1) `getMax()`? Does one extra stack still suffice? (Answer: you need a third stack -- a max stack. The pattern extends cleanly. Each auxiliary stack tracks one aggregate.)
**Difficulty:** Intermediate
**What interviewers are really testing:** Whether you understand the *amortized analysis* behind monotonic stacks. Most candidates can code the solution but cannot explain why it is O(n) -- they just say "we visit each element once." The real proof requires reasoning about total push/pop operations across the entire traversal.
**Strong answer:**
* **Naive approach:** For each element, scan right until you find something greater. Worst case (sorted descending like `[5, 4, 3, 2, 1]`), every element scans to the end. That is O(n^2).
* **Monotonic stack approach:** Maintain a stack where elements are in decreasing order (from bottom to top). For each new element, pop everything smaller -- those popped elements just found their "next greater." Then push the current element.
* **Why O(n):** Each element is pushed exactly once and popped at most once. Total operations across the entire traversal: at most 2n. The while loop inside the for loop looks like it could be O(n) per iteration, but **amortized across all iterations**, the total pops cannot exceed n because we never pop something that was not previously pushed.
* **The way I think about it:** The stack is like a waiting room. Elements sit in the waiting room until someone greater shows up. Once they are "resolved" (popped), they never come back. Since each element enters and exits the waiting room exactly once, total work is O(n).
* **Key detail:** Store **indices**, not values. You almost always need the index for distance calculations (like in Daily Temperatures) or to write results back to an array.
```python theme={null}
# Each element enters the stack once, exits at most once = O(2n) = O(n)
for i in range(len(nums)):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop() # This element exits forever
result[idx] = nums[i] # Its "next greater" is nums[i]
stack.append(i) # This element enters once
```
**Red flag answer:** "It is O(n) because we iterate through the array once." This ignores the inner while loop. If a candidate cannot explain why the while loop does not make it O(n^2), they do not understand amortized analysis. Another red flag: confusing "monotonically increasing" and "monotonically decreasing" stacks -- get the direction wrong and the algorithm finds next *smaller* instead of next *greater*.
**Follow-ups:**
1. When would you use a monotonic *increasing* stack versus a monotonic *decreasing* stack? Give a concrete problem for each. (Answer: decreasing stack for "next greater element" -- you pop when you see something bigger. Increasing stack for "next smaller element" or "largest rectangle in histogram" -- you pop when you see something smaller.)
2. How would you adapt this for a *circular* array where the "next greater" can wrap around? (Answer: iterate through the array twice -- conceptually `2n` elements -- using `i % n` for indexing. Only push during the first pass. The second pass resolves elements whose next greater wraps around.)
**Difficulty:** Senior
**What interviewers are really testing:** This is the hardest standard stack problem and a favorite at FAANG interviews. The interviewer wants to see if you can explain the *width calculation* on pop -- specifically, why `width = i - stack[-1] - 1` (not `i - popped_index`). Getting the width wrong is the most common bug, and understanding it requires grasping what the stack *invariant* guarantees about the elements between indices.
**Strong answer:**
* **Why monotonic increasing:** We want to find, for each bar, the largest rectangle using that bar as the shortest bar. A bar can extend left and right as long as all bars in that range are at least as tall. A monotonic increasing stack guarantees that when we pop a bar, everything between the new stack top and the current index is at least as tall as the popped bar.
* **The pop moment:** When `heights[i] < heights[stack[-1]]`, the bar at `stack[-1]` can no longer extend right (it hit something shorter). So we pop it and calculate its rectangle.
* **Width calculation -- the tricky part:** After popping index `j`, the width is NOT `i - j`. It is `i - stack[-1] - 1` (or `i` if the stack is empty). Why? Because everything between the new stack top and `i` was already popped earlier, meaning those bars were all taller than `heights[j]`. So the rectangle of height `heights[j]` extends all the way from `stack[-1] + 1` to `i - 1`.
* **Sentinel trick:** Append a `0` to the end of the heights array. This forces all remaining elements to be popped, avoiding a separate cleanup loop after the main iteration. It is a clean simplification that interviewers appreciate.
* **Example:** For `[2, 1, 5, 6, 2, 3]`, when we hit the second `2` (index 4), we pop `6` (index 3): height = 6, width = `4 - 2 - 1 = 1`, area = 6. Then pop `5` (index 2): height = 5, width = `4 - 1 - 1 = 2`, area = 10. That `width = 2` is the key -- it includes index 3 because the `6` at index 3 was taller than `5`.
```python theme={null}
# The sentinel avoids cleanup code after the loop
heights.append(0)
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# Width extends from (new stack top + 1) to (i - 1)
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
```
**Red flag answer:** Using `width = i - popped_index` instead of `i - stack[-1] - 1`. This is the single most common bug -- it gives wrong answers when multiple bars have been popped. If a candidate cannot explain why previously-popped bars contribute to the width, they do not understand the invariant. Another red flag: not mentioning the sentinel trick and instead having a messy cleanup loop that handles edge cases differently.
**Follow-ups:**
1. How would you extend this to the Maximal Rectangle problem (LC 85), where you find the largest rectangle of 1s in a binary matrix? (Answer: treat each row as a histogram where the bar height is the number of consecutive 1s above. Run the largest rectangle algorithm on each row's histogram. O(rows \* cols) total.)
2. What is the relationship between this problem and Trapping Rain Water? Can you use the same stack technique? (Answer: Trapping Rain Water uses a monotonic *decreasing* stack -- you pop when you see something *taller* because it means a valley has been found. The height calculation uses the min of the two boundaries minus the popped bar's height, and width is computed the same way. Same technique, opposite monotonicity.)
**Difficulty:** Intermediate
**What interviewers are really testing:** Whether you can manage **multiple types of state** on the stack simultaneously. Parentheses matching only tracks one thing (the bracket type). Decode String requires tracking both a string accumulator and a repeat count, and correctly restoring state when you pop. This tests stack-as-state-machine thinking.
**Strong answer:**
* **Why it is harder:** In valid parentheses, the stack stores single characters. Here, we need to store *context* -- the string we were building and the multiplier we saw before the `[`. When we hit `]`, we need to restore both.
* **The pattern:** Maintain `current_string` and `current_num` as running accumulators. On `[`, push `(current_string, current_num)` onto the stack and reset both. On `]`, pop the saved state and compute `prev_string + current_string * num`. On digits, build the number. On letters, append to `current_string`.
* **Why two accumulators, not just one stack?** You could use a single stack and push everything (digits, brackets, characters), but then the `]` handler has to scan backwards through the stack to find the matching `[` and extract the number. Using separate accumulators makes the `]` handler O(1) instead of O(k) where k is the segment length.
* **Nested example walkthrough for `3[a2[bc]]`:**
* Read `3` -> `current_num = 3`
* Read `[` -> push `("", 3)`, reset to `current_str = "", current_num = 0`
* Read `a` -> `current_str = "a"`
* Read `2` -> `current_num = 2`
* Read `[` -> push `("a", 2)`, reset to `current_str = "", current_num = 0`
* Read `b`, `c` -> `current_str = "bc"`
* Read `]` -> pop `("a", 2)`, `current_str = "a" + "bc" * 2 = "abcbc"`
* Read `]` -> pop `("", 3)`, `current_str = "" + "abcbc" * 3 = "abcbcabcbcabcbc"`
```python theme={null}
# Stack stores (previous_string, repeat_count) tuples
for char in s:
if char == '[':
stack.append((current_str, current_num))
current_str, current_num = "", 0
elif char == ']':
prev_str, num = stack.pop()
current_str = prev_str + current_str * num
```
**Red flag answer:** Trying to use regex or recursion without being able to explain the stack-based iterative approach. The recursive solution works but interviewers specifically ask this to test iterative stack thinking. Another red flag: forgetting to handle multi-digit numbers (e.g., `12[a]` -- you need `current_num = current_num * 10 + int(char)`, not just `int(char)`).
**Follow-ups:**
1. What if the encoding can have nested brackets *without* a number prefix, like `[abc]` meaning repeat once? How does your code handle this edge case? (Answer: initialize `current_num` to default 1 when pushing, or treat missing numbers as 1. The code needs a minor tweak -- check if `current_num == 0` on `[` and default it.)
2. What is the time complexity? It is not O(n) where n is the input length -- explain why. (Answer: the output string can be exponentially larger than the input. For `10[10[10[a]]]`, the input is \~15 characters but the output is 1000 characters. Time is O(output\_length), which can be much larger than input length. This matters for memory allocation decisions in production.)
**Difficulty:** Senior
**What interviewers are really testing:** Whether you understand how stacks can implement a **state machine** that evaluates expressions by saving and restoring evaluation context at each nesting level. The two-value push (result + sign) is the non-obvious insight that most candidates miss, and it reveals whether you can think about composing sub-expression results.
**Strong answer:**
* **The challenge:** Parentheses create nested evaluation contexts. The expression `1 - (2 + 3)` requires evaluating `2 + 3 = 5` in its own context, then applying the `-` sign from the outer context. You need to "pause" the outer evaluation, compute the inner one, and "resume."
* **Why push both result and sign:** On `(`, push the *running result so far* and the *sign before the parenthesis*. Reset result to 0 and sign to 1. This creates a clean inner context. On `)`, finish the inner computation, then multiply by the saved sign and add to the saved result. This "merges" the inner result back into the outer context.
* **Walkthrough of `1 - (2 + 3)`:**
* Read `1` -> result = 1
* Read `-` -> sign = -1
* Read `(` -> push `(1, -1)`, reset result = 0, sign = 1
* Read `2` -> result = 2
* Read `+` -> sign = 1
* Read `3` -> result = 5
* Read `)` -> pop `(1, -1)`, result = `5 * (-1) + 1 = -4`
* **Why not Shunting-yard or RPN conversion?** Those work but are overkill for `+`, `-`, `(`, `)`. The direct evaluation with a stack is simpler and avoids building an intermediate representation. If the problem adds `*` and `/` with precedence, *then* Shunting-yard becomes worth the added complexity.
```python theme={null}
elif char == '(':
stack.append(result) # Save outer result
stack.append(sign) # Save sign before '('
result = 0 # Fresh inner context
sign = 1
elif char == ')':
result += sign * number
number = 0
result *= stack.pop() # Apply saved sign
result += stack.pop() # Add to saved result
```
**Red flag answer:** "Convert to Reverse Polish Notation first, then evaluate." This is a valid approach but shows the candidate cannot reason about direct evaluation and may be falling back on the only technique they memorized. A worse red flag: not understanding why the sign is pushed -- saying "we just push the result" and then getting wrong answers on expressions like `1 - (2 - 3)`.
**Follow-ups:**
1. How would you extend this to support `*` and `/` with correct operator precedence? (Answer: you now need two stacks -- one for operands and one for operators -- or you need to process `*` and `/` immediately while deferring `+` and `-` until later. Alternatively, convert to RPN with Shunting-yard then evaluate.)
2. What happens with deeply nested expressions like `((((1 + 2))))` -- is there a stack depth concern? (Answer: stack depth equals nesting depth. For user-generated input, you should add a max nesting depth check to prevent stack overflow in production. Compilers typically limit nesting depth for this reason.)
**Difficulty:** Intermediate (but reveals production-level thinking)
**What interviewers are really testing:** Whether you have actually *debugged* stack code in practice or just written it once for a problem set. Candidates with real experience can rattle off specific failure modes and prevention strategies. This tests engineering maturity more than algorithmic knowledge.
**Strong answer:**
* **Bug #1: Empty stack access.** Calling `peek()` or `pop()` on an empty stack. This is the single most common runtime crash. Prevention: always guard with `if stack` (Python), `!stack.isEmpty()` (Java), or `!stk.empty()` (C++) before every access. Make it a reflex, not a conscious decision.
* **Bug #2: Forgetting remaining elements.** After the main loop, the stack may still contain unprocessed elements. In "next greater element," remaining elements have no greater element to their right and should be set to -1. In "largest rectangle," remaining bars still need their areas calculated. Prevention: either process the stack after the loop or use a **sentinel value** (append 0 to the array) that forces everything to pop.
* **Bug #3: Storing values instead of indices.** If you push values instead of indices, you lose positional information needed for distance calculations. `Daily Temperatures` returns *how many days* until warmer, not the temperature itself. Prevention: default to storing indices; you can always look up the value via `arr[index]`.
* **Bug #4: Wrong monotonic direction.** Using an increasing stack when you need decreasing (or vice versa). This flips the problem from "next greater" to "next smaller." Prevention: before coding, explicitly write a comment like `# monotonic decreasing: pop when current > top` and verify against a small example.
* **Bug #5: Off-by-one in width calculations.** In largest rectangle, the width is `i - stack[-1] - 1`, not `i - popped_index`. This is because previously-popped elements between the new top and `i` were taller. Prevention: trace through a small example (e.g., `[2, 1, 5, 6, 2, 3]`) on paper before coding.
```python theme={null}
# Defensive stack template
stack = []
for i in range(len(arr)):
while stack and arr[i] > arr[stack[-1]]: # Guard: 'stack' check
idx = stack.pop()
result[idx] = arr[i]
stack.append(i) # Always store indices
# Process remaining -- do not forget this
while stack:
idx = stack.pop()
result[idx] = -1 # No next greater element
```
**Red flag answer:** "I just test with examples and fix bugs as they come up." This is not a strategy, it is hope. A strong candidate has a **mental checklist** they apply to every stack solution before running it. Another red flag: not knowing about the sentinel trick for avoiding the cleanup loop.
**Follow-ups:**
1. In Java, `Stack` uses `Integer` objects. What subtle bug can occur when comparing stack top with a value using `==` instead of `.equals()`? (Answer: `==` compares object references, not values. For integers outside the cached range of -128 to 127, two `Integer` objects with the same value can have different references. `stack.peek() == value` may return false even when the values match. Always use `.equals()` or unbox explicitly.)
2. How do you test a stack-based solution efficiently? What edge cases do you always check? (Answer: empty input, single element, all elements the same, strictly increasing input, strictly decreasing input, and the input that triggers the worst-case stack depth. These cover all boundary conditions for stack behavior.)
**Difficulty:** Senior
**What interviewers are really testing:** Whether you understand that the same problem can be solved with fundamentally different data structures, and whether you have the judgment to articulate *when each approach is superior*. The stack approach processes water in horizontal layers (bottom-up), while two pointers process it in vertical columns. Understanding both reveals deep algorithmic thinking.
**Strong answer:**
* **How the stack approach works:** Maintain a monotonic decreasing stack of indices. When `height[i] > height[stack[-1]]`, a valley has been found. Pop the valley bottom, then calculate the water trapped between the new stack top (left boundary) and the current index (right boundary).
* **Water calculation on pop:** `height = min(height[stack[-1]], height[i]) - height[popped]` (bounded height minus valley floor). `width = i - stack[-1] - 1`. Water for this layer = `height * width`. This adds water in **horizontal layers**, not vertical columns.
* **Key difference from two-pointer:** Two pointers calculate water column by column (vertical slices): for each position, `water += min(left_max, right_max) - height[i]`. The stack calculates water layer by layer (horizontal slices): for each valley, compute the rectangular strip of water trapped.
* **When to prefer the stack:**
* When the input is a **stream** and you do not have the full array upfront. The stack processes left-to-right and does not need a right-to-left pass.
* When the problem variation asks "how many distinct pools of water are formed" -- the stack naturally segments water into contiguous pools as each valley is processed.
* **When to prefer two pointers:** When you need O(1) space (the stack is O(n) worst case) and you have the full array.
```python theme={null}
stack = []
water = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom = stack.pop()
if not stack: # No left boundary
break
h = min(height[stack[-1]], height[i]) - height[bottom]
w = i - stack[-1] - 1
water += h * w
stack.append(i)
```
**Red flag answer:** "I would just use two pointers, the stack approach is unnecessary." This shows inflexibility and suggests the candidate only knows one approach. Even worse: confusing the monotonic direction -- using an increasing stack instead of decreasing, which would find valleys incorrectly.
**Follow-ups:**
1. What is the worst-case space complexity of the stack approach? Give a concrete input that triggers it. (Answer: O(n) when the input is strictly decreasing like `[5, 4, 3, 2, 1]`. Nothing gets popped until you hit a taller bar, so all indices accumulate on the stack.)
2. If the input heights can be floating-point numbers, does the stack approach still work correctly? Are there precision concerns? (Answer: the algorithm works identically. However, floating-point addition is not associative, so the order in which horizontal layers are summed can cause tiny precision differences compared to the two-pointer approach. For financial or engineering calculations, you might need to use `decimal` types or track an error bound.)
**Difficulty:** Foundational (but the system design nuance elevates it)
**What interviewers are really testing:** Whether you can bridge algorithmic knowledge to a real system design. This also tests whether you think about **invalidation** -- the forward stack must be cleared on new navigation, which is a state management concern that trips up candidates who only think about push/pop.
**Strong answer:**
* **Two stacks:** A `back_stack` and a `forward_stack`. The current page is a separate variable (not on either stack).
* **Navigate to new URL:** Push current page onto `back_stack`. Set current = new URL. **Clear the forward stack entirely.** This is the critical insight -- visiting a new page invalidates all forward history. This is the same behavior you see in every browser.
* **Back button:** Push current page onto `forward_stack`. Pop `back_stack` and set it as current.
* **Forward button:** Push current page onto `back_stack`. Pop `forward_stack` and set it as current.
* **Edge cases:** Back with empty `back_stack` -> disable the button (no-op). Same for forward. This maps to how browsers grey out the buttons.
* **Real-world considerations:** In production, you would not store full page objects on the stack -- you would store URLs or session history entry IDs. Browsers also cap history depth (Chrome limits to \~50 entries per tab) to prevent memory bloat. You would also handle `pushState`/`replaceState` from the History API, which adds entries without actual navigation.
```python theme={null}
class BrowserHistory:
def __init__(self, homepage):
self.current = homepage
self.back_stack = []
self.forward_stack = []
def visit(self, url):
self.back_stack.append(self.current)
self.current = url
self.forward_stack.clear() # Invalidate forward history
def back(self):
if not self.back_stack:
return self.current # No-op
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
```
**Red flag answer:** "Use one stack and an index pointer." While this works (and is actually how LeetCode 1472 models it), it does not demonstrate understanding of why two stacks are the natural model for back/forward navigation. Another red flag: forgetting to clear the forward stack on new navigation -- this would allow users to go "forward" to a page that is no longer part of the navigation path.
**Follow-ups:**
1. If the user clicks back 5 times rapidly, should you render all 5 intermediate pages or skip to the final destination? How does this affect your design? (Answer: in a real browser, each back is rendered, but rapid clicks debounce and the intermediate renders may be interrupted. Your stack logic stays the same -- the rendering layer handles the optimization.)
2. How would you add a `steps` parameter to back and forward (like LC 1472) so the user can go back N pages at once? What is the time complexity? (Answer: pop min(N, stack size) elements in a loop, pushing each to the other stack. O(N) per call. You could optimize to O(1) with an array + pointer instead of two stacks, which is why the LC solution often uses that model.)
**Difficulty:** Senior
**What interviewers are really testing:** Whether you can extend a known pattern to handle a **structural constraint** (circularity). The "iterate twice" trick is not obvious, and explaining *why* it is correct requires understanding that one full extra pass is sufficient to resolve all wrap-around dependencies. This also tests modular arithmetic fluency.
**Strong answer:**
* **The problem with circularity:** In a linear array, elements at the end have no "next greater" to the right. In a circular array, the search wraps around -- the next greater element for the last element could be the first element.
* **The trick:** Iterate `2n` times using `i % n` for indexing. The first pass (`i = 0` to `n-1`) works exactly like the linear version. The second pass (`i = n` to `2n-1`) revisits elements, allowing wrap-around resolution. Only push indices during the first pass (`i < n`), or push `i % n` throughout -- but only write results for indices less than `n`.
* **Why one extra pass suffices:** After the first pass, the stack contains indices whose next greater element was not found in the linear scan. During the second pass, each of these elements gets compared against elements from the start of the array. Since the second pass covers the entire array, every element gets a chance to be the "next greater" for every unresolved element. No element needs more than one full wrap-around to find its answer (or confirm none exists).
* **What about elements that truly have no next greater?** In a circular array, an element has no next greater only if it is the maximum of the entire array. After `2n` iterations, such elements remain on the stack. Their result stays as the initialized `-1`.
```python theme={null}
def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[i % n] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # Only push real indices
return result
```
**Red flag answer:** "Just duplicate the array and run the normal algorithm." While conceptually similar, actually concatenating the array wastes O(n) space and creates confusion about which indices are "real." Using `i % n` achieves the same effect with O(1) extra space. Another red flag: iterating `3n` or more times "just to be safe" -- this shows the candidate does not understand why `2n` is exactly sufficient.
**Follow-ups:**
1. What is the time and space complexity? Is the `2n` iteration still O(n)? (Answer: yes, O(n) time -- each of the n elements is pushed once and popped at most once. The second pass only causes pops, no new pushes. Space is O(n) for the stack and result array.)
2. What if instead of "next greater," I ask for the "next greater element that is at least K positions away" in a circular array? Does the monotonic stack still work directly? (Answer: not directly. The monotonic stack resolves the *nearest* next greater. For a minimum-distance constraint, you would need to delay processing -- only pop an element when the current index is at least K positions ahead of it. This requires careful index arithmetic with the modular wrapping.)
## Interview Q\&A Rapid-Fire (Rich Format)
The four problems below mirror the format you will see in our other DSA chapters: strong answer framework, real LeetCode example with full code, three senior follow-ups, common wrong answers, and further reading.
**Strong Answer Framework:**
1. **Identify the constraint.** "All four operations -- push, pop, top, getMin -- must be O(1). A naive single stack makes getMin O(n)."
2. **Introduce the auxiliary structure.** "I will keep a parallel min-stack tracking the running minimum at every height of the main stack."
3. **Push rule.** Push to main always. Push to min-stack only if the new value is `<=` the current min (the `<=` is critical for duplicates).
4. **Pop rule.** Pop main always. If the popped value equals the min-stack top, pop min-stack too.
5. **Justify `<=` vs `<`.** Trace `[2, 0, 0]`: with `<`, popping the first `0` removes it from the min-stack and `getMin` returns `2` while a `0` is still on main. With `<=`, the second `0` is also pushed onto min-stack, preserving correctness.
**Real LeetCode Example -- LC 155: Min Stack**
```python theme={null}
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]: # <= for duplicates
self.min_stack.append(val)
def pop(self) -> None:
top = self.stack.pop()
if top == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
```
Time O(1) for every operation. Space O(n) worst case (strictly decreasing input).
**Senior Follow-up 1:** "Can you achieve O(1) extra space (not O(n))?" -- Yes, by storing differences. Push `val - current_min` onto a single stack. When the stored value is negative, it signals a new min (and you can recover the previous min by subtraction). Clever but fragile -- integer overflow with extreme values is a real concern.
**Senior Follow-up 2:** "What if I also need O(1) getMax?" -- Add a third stack (max-stack) following the same pattern, push when `val >= max_stack[-1]`. Each auxiliary stack tracks one aggregate. The pattern composes cleanly.
**Senior Follow-up 3:** "What is the worst-case extra memory?" -- O(n) when the input is strictly decreasing. Every push to main also pushes to min-stack. Best case is strictly increasing input, where min-stack only holds the very first element.
**Common Wrong Answers:**
* "Track the minimum in a single variable" -- breaks on pop. After popping the current min, you do not know the new min without scanning.
* "Use `<` instead of `<=` for the min-stack push condition" -- silently wrong on duplicate minimums.
* "Scan the stack on getMin" -- O(n) per call, fails the constraint.
**Further Reading:**
* [LC 155: Min Stack](https://leetcode.com/problems/min-stack/)
* [LC 716: Max Stack](https://leetcode.com/problems/max-stack/)
* [LC 895: Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/)
**Strong Answer Framework:**
1. **Recognize the postfix advantage.** "RPN is unambiguous -- no parentheses, no precedence rules. The stack evaluates it in one linear pass."
2. **State the algorithm.** Iterate tokens. If number, push. If operator, pop two operands, apply, push result.
3. **Order matters for non-commutative operators.** For `a - b`, the second pop is `a` (the left operand) and the first pop is `b` (the right operand). Same for division.
4. **Handle integer division semantics.** Some problems require truncation toward zero (LC 150 specifically), not Python's floor division.
5. **Verify the final state.** After processing all tokens, exactly one value remains on the stack: the result.
**Real LeetCode Example -- LC 150: Evaluate Reverse Polish Notation**
```python theme={null}
def evalRPN(tokens):
stack = []
for tok in tokens:
if tok in {'+', '-', '*', '/'}:
b = stack.pop() # right operand popped first
a = stack.pop() # left operand popped second
if tok == '+': stack.append(a + b)
elif tok == '-': stack.append(a - b)
elif tok == '*': stack.append(a * b)
else: # division: truncate toward zero
stack.append(int(a / b)) # NOT a // b
else:
stack.append(int(tok))
return stack[0]
```
Time O(n), space O(n).
**Senior Follow-up 1:** "Why `int(a / b)` instead of `a // b` in Python?" -- Python's `//` is floor division, which rounds toward negative infinity. The problem requires truncation toward zero. `int(a / b)` truncates correctly: `int(-7 / 2) == -3` (truncated), while `-7 // 2 == -4` (floored). This is a common subtle bug.
**Senior Follow-up 2:** "How would you handle infix expressions instead of postfix?" -- Convert with the shunting-yard algorithm: use two stacks (one for operators, one for output). Pop higher-or-equal precedence operators when pushing a new operator. Or evaluate directly with two stacks (operands and operators) and the same precedence logic.
**Senior Follow-up 3:** "What if the expression has function calls like `max(a, b)` or unary operators like `-x`?" -- Extend the parser: function names go on the operator stack with their argument count. Unary minus is detected by context (no preceding operand). The shunting-yard algorithm handles all this; LeetCode rarely tests it but production calculators must.
**Common Wrong Answers:**
* "Pop in the wrong order" -- `a - b` becomes `b - a`. The interviewer is watching for whether you say "left operand popped second" out loud.
* "Use `//` for division" -- wrong for negative numbers (LC 150 specifically tests this).
* "Build a parse tree first" -- correct but overkill; the stack handles RPN in one pass with no tree.
**Further Reading:**
* [LC 150: Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)
* [LC 224: Basic Calculator](https://leetcode.com/problems/basic-calculator/)
* [LC 227: Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/)
**Strong Answer Framework:**
1. **Articulate the LIFO insight.** "The most recently opened bracket must be the first one closed -- exactly the LIFO property of a stack."
2. **Reject the counter approach.** A single counter passes `([)]` (balanced counts but invalid nesting). Only a stack tracks order.
3. **Set up a closer-to-opener map** for O(1) match lookup.
4. **One pass through the string.** Push openers; on closers, the stack top must be the matching opener.
5. **End-state check.** Empty stack means valid -- leftover openers mean unclosed brackets.
**Real LeetCode Example -- LC 20: Valid Parentheses**
```python theme={null}
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in '([{':
stack.append(c)
else: # c is a closer
if not stack or stack.pop() != pairs[c]:
return False
# NB: empty-stack guard is required to avoid IndexError on stray closers
return not stack
```
Time O(n), space O(n).
**Senior Follow-up 1:** "Now make this incremental -- support `addChar(c)` and `isValid()` queries." -- Same stack, but expose it as state. `addChar` does the push or pop; `isValid` checks if the stack is empty AND no mismatch has occurred. Keep a `is_dirty` flag for early failures.
**Senior Follow-up 2:** "What if the input contains non-bracket characters like 'a + (b \* c)'?" -- Skip characters not in the opener set or closer map. Algorithm is otherwise unchanged.
**Senior Follow-up 3:** "Return the index of the first mismatch instead of true/false." -- Track indices alongside characters on the stack. On mismatch, the current index is the answer. On leftover openers at the end, the bottom of the stack gives the earliest unclosed index.
**Common Wrong Answers:**
* "Use one counter per bracket type" -- passes `([)]`, which is wrong.
* "Use regex to repeatedly remove `()`, `[]`, `{}`" -- works for matched-only but is O(n^2) in the worst case.
* "Forget the empty-stack check" -- crashes on inputs that start with a closer like `)`.
**Further Reading:**
* [LC 20: Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
* [LC 921: Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/)
* [LC 32: Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/)
**Strong Answer Framework:**
1. **Recognize the pattern.** "This is 'next greater element' but instead of recording the value, I record the day distance."
2. **Brute force first.** O(n^2) -- for each day, scan forward. Too slow.
3. **Monotonic stack of indices.** Days waiting for warmer weather sit on the stack; today's temperature pops every day on top that is colder.
4. **Why indices, not values.** We need `i - j` to compute the wait distance.
5. **Default to 0.** Days remaining on the stack at the end never found a warmer day -- the array's default zero already handles them.
6. **Prove O(n) amortized.** Each day is pushed once and popped at most once.
**Real LeetCode Example -- LC 739: Daily Temperatures**
```python theme={null}
def daily_temperatures(temps):
n = len(temps)
result = [0] * n
stack = [] # indices of waiting days
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j # day distance, not temperature value
stack.append(i)
return result
```
Time O(n), space O(n).
**Senior Follow-up 1:** "Solve in O(1) extra space (not counting the output array)." -- Traverse right-to-left. For each day, walk forward using the already-computed answers as jump pointers (similar to skip-list traversal). Implementation is trickier but achieves the constant-space goal.
**Senior Follow-up 2:** "Now I want days until a STRICTLY COLDER day." -- Flip the comparison: monotonic increasing stack, pop when `temps[i] < temps[stack[-1]]`. The skeleton is identical; only the comparison flips.
**Senior Follow-up 3:** "Apply this in a streaming setting -- temperatures arrive one per day." -- This becomes LC 901 (Online Stock Span). Maintain a stack of `(value, span_count)` pairs. On a new value, accumulate spans of all popped smaller values into the current span. Amortized O(1) per call.
**Common Wrong Answers:**
* "Brute force scanning forward from each day" -- O(n^2), times out.
* "Push values, not indices" -- cannot compute the distance `i - j`.
* "Forget that remaining stack elements should map to 0" -- relying on default initialization is fine but candidates often add a redundant cleanup loop and break it.
**Further Reading:**
* [LC 739: Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)
* [LC 496: Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)
* [LC 901: Online Stock Span](https://leetcode.com/problems/online-stock-span/)