Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Stacks & Monotonic Stack

Stacks solve matching and undo problems, and a monotonic stack answers 'next greater or smaller' for every index in one O(n) pass. Learn both shapes, why each index is pushed and popped once, and watch Valid Parentheses, Daily Temperatures and Largest Rectangle in Histogram animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 9 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Stack operations in Python, TypeScript and C#
Matching, evaluation and simulation with a stack
The monotonic stack template and its variants
Six LeetCode problems up to Largest Rectangle in Histogram

📚 Before you start

Part 1The Pattern

A stack is last-in, first-out: push and pop at one end in O(1). In interviews it shows up in two ways. The first is matching and undo: brackets, nested structures, expression evaluation, backtracking a path. The second is the monotonic stack: keeping a stack whose values are always increasing (or decreasing) answers "next greater/smaller element" questions for every index in one O(n) pass.

A monotonic decreasing stack popping smaller values when a larger one arrives

1Stack Basics per Language

	Python	TypeScript	C#
create	`stack = []`	`const stack: T[] = []`	`var stack = new Stack<T>()`
push	`stack.append(x)`	`stack.push(x)`	`stack.Push(x)`
pop	`stack.pop()`	`stack.pop()`	`stack.Pop()`
peek	`stack[-1]`	`stack[stack.length - 1]` (or `.at(-1)`)	`stack.Peek()`
empty?	`not stack`	`stack.length === 0`	`stack.Count == 0`

2Recognition Cues

Matching: "valid parentheses", "decode 3[a2[c]]", "simplify a path", "remove adjacent duplicates".
Evaluation: "evaluate reverse Polish notation", "basic calculator".
Monotonic: "next greater/smaller element", "how many days until a warmer temperature", "largest rectangle in a histogram", "stock span", "remove k digits to make the smallest number".

3Monotonic Stack Template

typescript

function nextGreater(nums: number[]): number[] {
  const res = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) res[stack.pop()!] = nums[i];
    stack.push(i);
  }
  return res;
}

python

def next_greater(nums):
    """For each i, the next element to the right that is larger (-1 if none)."""
    res = [-1] * len(nums)
    stack = []                          # indices; their values are decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x        # x is the answer for everything it pops
        stack.append(i)
    return res

Why it's O(n): every index is pushed once and popped at most once. When a new element arrives, it pops every smaller element: for each of those it is exactly the next greater element, because anything between them was smaller and has already been popped.

Variants:

Want	Stack keeps	Pop while
next greater	decreasing values	`top < x`
next smaller	increasing values	`top > x`
previous greater/smaller	same, read the top after popping	same
circular array	iterate `2n` times using `i % n`	same

4Histogram Thinking

For each bar, the largest rectangle using it as the shortest bar extends left and right until a smaller bar. An increasing stack gives both boundaries: when bar i pops bar j, then i is j's right boundary and the new top is j's left boundary. That's Largest Rectangle in Histogram (84) and, row by row, Maximal Rectangle (85).

⚠️ Common Pitfalls

Pushing values instead of indices when you need distances or widths.
Popping an empty stack: check before peeking or popping, and check that the stack is empty at the end (unmatched brackets).
Strict vs non-strict comparison with duplicates: < vs <= changes which equal element is "next".
Forgetting to flush the stack at the end (append a sentinel 0 bar in histogram problems).
Using list.pop(0) for a queue; that's not a stack operation and costs O(n).

📋 Quick Reference

text

Matching: push openers; on closer, top must match → pop; end: stack empty
Monotonic (next greater): for i: while st and a[st[-1]] < a[i]: ans[st.pop()] = a[i]; st.append(i)
Histogram: increasing stack + sentinel 0; width = i - st[-1] - 1 after pop
Each index pushed/popped once → O(n)

Part 2Interview Problems

Six problems: matching, design, evaluation and simulation with a plain stack, then the monotonic stack for next-warmer days and the largest rectangle in a histogram.

1Valid Parentheses (LeetCode 20)

🟢 Easy. Given a string of ()[]{}, return true if brackets are closed in the correct order.

text

s = "{[]}" → true · s = "([)]" → false

Approach. Push each opener. For a closer, the top of the stack must be the matching opener; pop it. At the end the stack must be empty.

Complexity. O(n) time, O(n) space.

typescript

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else stack.push(c);
  }
  return stack.length === 0;
}

python

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return not stack

2Min Stack (LeetCode 155)

🟠 Medium. Design a stack supporting push, pop, top and getMin, all in O(1).

text

push(-2), push(0), push(-3), getMin() → -3, pop(), top() → 0, getMin() → -2

Approach. Store pairs (value, minSoFar): each entry remembers the minimum of the stack at the time it was pushed, so getMin is just the top's second field, even after pops.

Complexity. O(1) per operation, O(n) space.

typescript

class MinStack {
  private items: [number, number][] = [];
  push(val: number): void {
    const curMin = this.items.length ? Math.min(val, this.items[this.items.length - 1][1]) : val;
    this.items.push([val, curMin]);
  }
  pop(): void { this.items.pop(); }
  top(): number { return this.items[this.items.length - 1][0]; }
  getMin(): number { return this.items[this.items.length - 1][1]; }
}

python

class MinStack:
    def __init__(self):
        self.items = []                     # (value, min so far)

    def push(self, val):
        cur_min = min(val, self.items[-1][1]) if self.items else val
        self.items.append((val, cur_min))

    def pop(self):
        self.items.pop()

    def top(self):
        return self.items[-1][0]

    def get_min(self):
        return self.items[-1][1]

3Evaluate Reverse Polish Notation (LeetCode 150)

🟠 Medium. Evaluate an arithmetic expression in postfix notation, e.g. ["2","1","+","3","*"]. Division truncates toward zero.

text

["4","13","5","/","+"] → 6

Approach. Push numbers. On an operator, pop the right operand first, then the left, apply, push the result.

Complexity. O(n) time, O(n) space.

typescript

function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  for (const t of tokens) {
    if ("+-*/".includes(t) && t.length === 1) {
      const b = stack.pop()!, a = stack.pop()!;
      stack.push(t === "+" ? a + b : t === "-" ? a - b : t === "*" ? a * b : Math.trunc(a / b));
    } else stack.push(Number(t));
  }
  return stack[stack.length - 1];
}

python

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in ("+", "-", "*", "/"):
            b, a = stack.pop(), stack.pop()
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))     # truncate toward zero (not //)
        else:
            stack.append(int(t))
    return stack[-1]

4Daily Temperatures (LeetCode 739)

🟠 Medium. For each day, return how many days until a warmer temperature (0 if never).

text

temps = [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

Approach. Monotonic decreasing stack of indices. A warmer day pops every colder day still waiting; the answer for a popped day is the index difference.

Complexity. O(n) time, O(n) space.

typescript

function dailyTemperatures(temps: number[]): number[] {
  const res = new Array(temps.length).fill(0), stack: number[] = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop()!;
      res[j] = i - j;
    }
    stack.push(i);
  }
  return res;
}

python

def daily_temperatures(temps):
    res = [0] * len(temps)
    stack = []                              # indices of days still waiting
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

5Asteroid Collision (LeetCode 735)

🟠 Medium. Positive asteroids move right, negative ones move left; on collision the smaller explodes (both if equal). Return the survivors.

text

[10,2,-5] → [10]

Approach. Stack of survivors. A left-moving asteroid collides with right-moving tops: pop smaller ones; if equal, pop and destroy both; if the top is bigger, the new one dies. Otherwise push.

Complexity. O(n) time, O(n) space.

typescript

function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    let alive = true;
    while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];
      if (top < -a) stack.pop();
      else { if (top === -a) stack.pop(); alive = false; }
    }
    if (alive) stack.push(a);
  }
  return stack;
}

python

def asteroid_collision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and stack and stack[-1] > 0:
            if stack[-1] < -a:
                stack.pop()                     # top explodes, keep checking
            elif stack[-1] == -a:
                stack.pop()                     # both explode
                alive = False
            else:
                alive = False                   # incoming explodes
        if alive:
            stack.append(a)
    return stack

6Largest Rectangle in Histogram (LeetCode 84)

🔴 Hard. Given bar heights of width 1, return the area of the largest rectangle in the histogram.

text

heights = [2,1,5,6,2,3] → 10   (bars 5 and 6, width 2)

Approach. Increasing stack of indices with a sentinel height 0 at the end. When bar i is lower than the top, pop the top j: its rectangle spans from the new top + 1 to i − 1 (everything between was taller), so width = i − stack[-1] − 1 (or i if the stack is empty).

Complexity. O(n) time, O(n) space.

typescript

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length && heights[stack[stack.length - 1]] > h) {
      const j = stack.pop()!;
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      best = Math.max(best, heights[j] * width);
    }
    stack.push(i);
  }
  return best;
}

python

def largest_rectangle_area(heights):
    stack = []
    best = 0
    for i, h in enumerate(heights + [0]):           # sentinel flushes the stack
        while stack and heights[stack[-1]] > h:
            j = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            best = max(best, heights[j] * width)
        stack.append(i)
    return best

🧠 Key takeaways

Stacks handle matching/undo (brackets, decoding, RPN) with O(1) push/pop.
A monotonic stack answers next greater/smaller for all indices in O(n).
Store indices, not values, when you need distances or widths.
Histogram: increasing stack + sentinel 0; width = i − top − 1 after popping.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_stacks_and_monotonic_stack_exercise_1.py

TS PY

algo_stacks_and_monotonic_stack_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why is the monotonic stack O(n) despite the inner while loop?

Amortized.

2. Next GREATER element uses a stack whose values are…

Smaller values get popped.

3. In RPN evaluation, after popping for '-', which operand is first?

b = pop(), a = pop(), a − b.

4. Why append a sentinel 0 in Largest Rectangle in Histogram?

Flush the stack.

Source: algo_stacks_and_monotonic_stack_theory_1.md, algo_stacks_and_monotonic_stack_theory_2.md · generated by tools/build_lessons.py