Stack

Stack — LIFO

Last In, First Out. Like a stack of plates. Powers bracket matching, undo operations, DFS, and monotonic problems.

Stack Operations (LIFO)
STACK (top →)
BOTTOM
Stack is empty. Push some values!
Stack state: []
Size: 0
Valid Parentheses — Step by Step
Stack: []
Type a bracket string and press Animate.
Monotonic Stack — Next Greater Element

For each element, find the next element that is greater. O(n) using decreasing monotonic stack.

Stack (indices): []
Result: []
Press Animate to start.

Monotonic Stack Logic

Decreasing Monotonic Stack
Maintain indices where values are decreasing. When a NEW element is bigger than the top → the new element IS the "next greater" for the top. Pop and record. Push current index.
Why O(n)?
Each element is pushed once and popped once. Total operations = 2n = O(n). Never re-examined.

Stack in Python

# Python list as stack — all O(1)
stack = []
stack.append(x)   # push
stack.pop()        # pop (crashes if empty!)
stack[-1]          # peek top
not stack          # True if empty
len(stack)         # size

# ── Valid Parentheses ──
def is_valid(s):
    stack = []
    match = {')':'(', ']':'[', '}':'{'}
    for c in s:
        if c in match:
            if not stack or stack[-1] != match[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return not stack
Always check empty before accessing
Check if not stack BEFORE stack[-1]. Accessing index on empty list raises IndexError.

Monotonic Stack + MinStack

# Next Greater Element — O(n)
def next_greater(arr):
    res = [-1] * len(arr)
    stack = []  # stores indices
    for i, val in enumerate(arr):
        while stack and arr[stack[-1]] < val:
            res[stack.pop()] = val
        stack.append(i)
    return res

# MinStack — O(1) get_min()
class MinStack:
    def __init__(self):
        self.stack = []; self.min_s = []
    def push(self, val):
        self.stack.append(val)
        m = val if not self.min_s else min(val, self.min_s[-1])
        self.min_s.append(m)
    def pop(self):
        self.stack.pop(); self.min_s.pop()
    def get_min(self): return self.min_s[-1]

LeetCode Problems

  • EasyValid ParenthesesClassic stack matching
  • EasyMin StackParallel min tracking stack
  • MediumDaily TemperaturesMonotonic decreasing stack
  • MediumNext Greater Element IICircular + monotonic stack
  • MediumEvaluate Reverse Polish NotationOperand stack
  • HardLargest Rectangle in HistogramMonotonic increasing stack
  • HardTrapping Rain WaterMonotonic stack or two pointer