Advanced Stack Interview Patterns: Monotonic Stack, Calculator, and Expression Parsing (2025)

Monotonic Stack Review

A monotonic stack maintains elements in strictly increasing or decreasing order. Increasing monotonic stack: pop when the incoming element is smaller (useful for finding next smaller element). Decreasing monotonic stack: pop when the incoming element is larger (useful for finding next greater element).

Next Greater Element I (LC 496) and II (LC 503)

LC 496 – find next greater element for elements of nums1 in nums2:

def nextGreaterElement(nums1, nums2):
    stack = []
    next_greater = {}
    for n in nums2:
        while stack and stack[-1] < n:
            next_greater[stack.pop()] = n
        stack.append(n)
    return [next_greater.get(n, -1) for n in nums1]

LC 503 – circular array, use mod to wrap indices:

def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

The double-pass trick (range(2 * n) with i % n) simulates wrapping around the array without actually duplicating it.

Largest Rectangle in Histogram (LC 84)

Classic monotonic stack problem. For each bar, we want to know: how far left and right can this bar extend at its full height?

Key insight: use an increasing monotonic stack. When we pop a bar because the current bar is shorter, the current bar defines the right boundary, and the new stack top defines the left boundary.

def largestRectangleArea(heights):
    stack = []  # indices, increasing by height
    max_area = 0
    heights.append(0)  # sentinel to flush stack
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Walk through example [2,1,5,6,2,3]:

i=0 (h=2): push 0. Stack: [0]
i=1 (h=1): pop 0 (h=2). Width = 1 (stack empty). Area = 2. Push 1. Stack: [1]
i=2 (h=5): push. Stack: [1,2]
i=3 (h=6): push. Stack: [1,2,3]
i=4 (h=2): pop 3 (h=6), width = 4-2-1=1, area=6. Pop 2 (h=5), width=4-1-1=2, area=10. Push 4. Stack: [1,4]
i=5 (h=3): push. Stack: [1,4,5]
i=6 (sentinel h=0): flush all. Max area = 10.

Basic Calculator II (LC 227)

Handle +, -, *, / without parentheses. Key insight: * and / bind tighter, so apply them immediately. Defer + and - by pushing signed values onto the stack.

def calculate(s):
    stack = []
    num = 0
    op = '+'
    s = s.replace(' ', '')
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        if (not c.isdigit()) or i == len(s) - 1:
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            elif op == '/':
                stack.append(int(stack.pop() / num))  # truncate toward zero
            op = c
            num = 0
    return sum(stack)

We always apply the previous operator (op) when we finish reading a number. The final sum(stack) handles all the deferred additions and subtractions.

Basic Calculator (LC 224) – With Parentheses

Parentheses require saving and restoring the sign context. Use a stack to store (current_result, current_sign) when entering a parenthesis, restore on closing.

def calculate(s):
    stack = []
    result = 0
    num = 0
    sign = 1
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '+':
            result += sign * num
            num = 0
            sign = 1
        elif c == '-':
            result += sign * num
            num = 0
            sign = -1
        elif c == '(':
            # Save current state, start fresh inside parens
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':
            result += sign * num
            num = 0
            result *= stack.pop()   # sign before the paren
            result += stack.pop()   # result before the paren
    result += sign * num
    return result

When we see (: push current result and sign, reset both. When we see ): finalize the inner result, multiply by the saved sign, add to saved outer result.

Decode String (LC 394)

Input: "3[a2[b]]", output: "abbbabbbabbb". Use two stacks: one for repeat counts, one for string prefixes built before the bracket.

def decodeString(s):
    count_stack = []
    str_stack = []
    current = ""
    k = 0
    for c in s:
        if c.isdigit():
            k = k * 10 + int(c)
        elif c == '[':
            count_stack.append(k)
            str_stack.append(current)
            current = ""
            k = 0
        elif c == ']':
            times = count_stack.pop()
            current = str_stack.pop() + current * times
        else:
            current += c
    return current

For "3[a2[b]]":

Read 3: k=3
Read [: push k=3, push current=””. Reset.
Read a: current=”a”
Read 2: k=2
Read [: push k=2, push current=”a”. Reset.
Read b: current=”b”
Read ]: times=2, current = “a” + “b”*2 = “abb”
Read ]: times=3, current = “” + “abb”*3 = “abbabbabb”

Remove K Digits (LC 402)

Given a number string and k removals, produce the smallest possible number. Greedy: use a monotonic increasing stack. When the current digit is smaller than the stack top and we still have removals left, pop (remove) the top digit.

def removeKdigits(num, k):
    stack = []
    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # If k > 0 after processing, remove from end (largest remaining)
    stack = stack[:-k] if k else stack
    # Strip leading zeros
    return "".join(stack).lstrip("0") or "0"

Example: num="1432219", k=3.

Push 1. Stack: [1]
Push 4. Stack: [1,4]
3 < 4, pop 4 (k=2). 3 > 1, push 3. Stack: [1,3]
2 < 3, pop 3 (k=1). 2 > 1, push 2. Stack: [1,2]
2 = 2, push. Stack: [1,2,2]
1 < 2, pop 2 (k=0). Stack: [1,2,1]. k=0 so stop.
Push 9. Final stack: [1,2,1,9]. Result: “1219”

The monotonic stack ensures we always prefer smaller leading digits, which minimizes the resulting number.

Interview Patterns Summary

Problem	Stack Type	Key Insight
Next Greater Element	Decreasing	Pop when current > top; map to next greater
Largest Rectangle	Increasing	Pop when current < top; use boundaries for width
Calculator II	Values	Apply * / immediately; defer + – to stack sum
Calculator I	State (result, sign)	Save/restore context at parentheses
Decode String	Two stacks	Separate stacks for counts and string prefixes
Remove K Digits	Increasing	Greedy pop when smaller digit found, k remaining