Core Idea
A stack (LIFO) is the right tool when the most recently seen element determines the action for the current element. The key intuition: a stack lets you look “back” efficiently at previous elements without rescanning. Most stack patterns run in O(n) amortized — each element is pushed and popped at most once.
Monotonic Stack (Next Greater Element)
Maintain a stack of indices in decreasing order of values. For each element, pop all elements smaller than the current one — the current element is the “next greater” for each popped element.
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indices of unresolved elements
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val # val is the next greater for nums[j]
stack.append(i)
return result
LC 496 (Next Greater Element I), LC 739 (Daily Temperatures — next warmer day), LC 503 (circular array: iterate 2n, index with i%n).
Largest Rectangle in Histogram (LC 84)
Maintain a monotonically increasing stack of indices. When a bar shorter than the top is encountered, pop and compute the rectangle width using the current index and the new top of stack.
def largestRectangleArea(heights):
heights.append(0) # sentinel to flush all remaining
stack = [-1] # sentinel for left boundary
max_area = 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
LC 85 (Maximal Rectangle): apply LC 84 on each row of a binary matrix treating column heights as the histogram.
Valid Parentheses and Matching
Push opening brackets; on closing bracket, check if top matches. Standard: LC 20. Extended: LC 1249 (Minimum Remove to Make Valid), LC 1963 (min swaps). For counting min additions: maintain open_count (unmatched opens) and close_count (unmatched closes). Scan left to right: ‘)’ with open_count=0 increments close_count; ‘)’ with open_count>0 decrements open_count; ‘(‘ increments open_count. Answer = open_count + close_count.
def minAddToMakeValid(s):
open_count = close_count = 0
for c in s:
if c == '(':
open_count += 1
elif open_count > 0:
open_count -= 1
else:
close_count += 1
return open_count + close_count
Min Stack (LC 155)
Maintain a second stack tracking the running minimum. On push: push min(val, min_stack.top()) to min_stack. On pop: pop from both stacks. getMin() = min_stack.top(). O(1) for all operations.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
m = val if not self.min_stack else min(val, self.min_stack[-1])
self.min_stack.append(m)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def getMin(self):
return self.min_stack[-1]
Evaluate Expression / Calculator
LC 224/227/772 (Basic Calculator series). Key insight for handling operator precedence: when you see ‘+’ or ‘-‘, push the current result onto the stack along with the sign. When you see ‘(‘, push the running result and sign onto the stack and reset. When you see ‘)’, pop and combine.
def calculate(s):
stack = []
num = 0
sign = 1
result = 0
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() # sign before (
result += stack.pop() # result before (
return result + sign * num
When to Use a Stack
- Matching pairs: parentheses, brackets, tags
- “Next greater/smaller” element: monotonic stack
- Largest rectangle / maximal area: histogram problems
- Undo/redo operations, expression evaluation
- DFS iterative implementation
- Any pattern where the current element interacts with the most recent unresolved element
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a monotonic stack and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A monotonic stack maintains elements in strictly increasing or strictly decreasing order. Elements are pushed and popped as new elements arrive, maintaining the invariant. Decreasing monotonic stack: for each new element, pop all elements smaller than it — the popped element's "next greater" is the current element. Use for: Next Greater Element (LC 496, 503), Daily Temperatures (LC 739), Trapping Rain Water (LC 42 — can use two-pointer but stack is intuitive), Stock Span Problem. Increasing monotonic stack: pop elements greater than current — finds "next smaller" or "previous smaller." Use for: Largest Rectangle in Histogram (LC 84), Remove K Digits (LC 402 — keep the smallest valid sequence). Amortized O(n): each element pushed and popped at most once.”}},{“@type”:”Question”,”name”:”How do you solve Largest Rectangle in Histogram (LC 84) with a stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a monotonically increasing stack of bar indices. For each bar i: while stack top has height >= current height h[i], pop index j. The width of the rectangle for bar j is: i – stack[-1] – 1 (current index minus the new top, which is the left boundary). Area = h[j] * width. Add a sentinel bar of height 0 at the end to flush all remaining bars. Initialize stack with -1 as a sentinel for the left boundary. This technique works because when we pop bar j, we know: its right boundary is current index i (first bar shorter than j), and its left boundary is the new stack top (last bar that remains, which is shorter than j). O(n) time, O(n) space. LC 85 (Maximal Rectangle in Binary Matrix) applies this per row.”}},{“@type”:”Question”,”name”:”How do you solve Trapping Rain Water (LC 42)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Three approaches: (1) Precompute arrays: left_max[i] = max height from index 0 to i, right_max[i] = max height from i to end. Water at i = min(left_max[i], right_max[i]) – height[i]. O(n) time, O(n) space. (2) Two pointers: maintain left_max and right_max as running values. Advance the pointer on the side with the smaller max — that side's water level is determined. O(n) time, O(1) space. (3) Monotonic stack: maintain a decreasing stack. When a taller bar is encountered, pop and compute water trapped between the popped bar and the current taller bar. O(n) time, O(n) space. The two-pointer approach is optimal and most interview-friendly.”}},{“@type”:”Question”,”name”:”How does the stack-based Basic Calculator work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For expressions with + – and parentheses (LC 224): maintain a running result, current number being parsed, current sign (+1 or -1), and a stack. When you see a digit: accumulate (num = num*10 + digit). When you see + or -: add sign*num to result, reset num, update sign. When you see (: push current result and sign onto stack, reset result=0 and sign=1. When you see ): complete the inner expression, multiply by the sign stored on stack (sign before the paren), add the result stored on stack (result before the paren). This handles nested parentheses naturally because the stack preserves the outer context. Return result + sign*num at the end.”}},{“@type”:”Question”,”name”:”When should you use a stack versus a deque for interview problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Stack (LIFO): use when only the most recently added element matters — parentheses matching, monotonic stack, expression evaluation, DFS iterative. Deque (double-ended queue, used as sliding window maximum): use when you need access to both ends — sliding window maximum (LC 239) maintains a decreasing deque where the front is always the max in the current window; elements falling outside the window are removed from the front, elements smaller than the new element are removed from the back. Rule of thumb: if you only push/pop from one end, use a stack. If you need to add/remove from both ends (or need a sliding window with front eviction), use a deque.”}}]}
Meta coding interviews frequently test stack and monotonic stack patterns. See common questions for Meta interview: stack and monotonic stack problems.
Amazon coding interviews test stack patterns and expression evaluation. Review problems for Amazon interview: stack and expression evaluation problems.
Atlassian coding rounds include stack and parentheses problems. See patterns for Atlassian interview: stack and bracket matching problems.