Jan 11, 2026

Stack

Overview

A stack processes the most recently added item first. It is useful when the current input resolves the most recent unfinished item or context. In this post, stacks preserve unmatched boundaries in Longest Valid Parentheses, save outer decoding state in Decode String, and hold partially evaluated terms in Basic Calculator III.

A second stack can maintain metadata for the main stack. Min Stack keeps both stacks at the same depth: one stores values and the other stores the minimum at each depth. This makes push, pop, top, and getMin all O(1).

A monotonic stack keeps values in increasing or decreasing order. Next Greater Element II and Daily Temperatures use decreasing stacks, so a larger current value resolves smaller entries. Largest Rectangle in Histogram uses an increasing stack, so a smaller current height supplies the right boundary for taller entries. Because each entry is pushed and popped only a constant number of times, these scans take O(n) time.

Templates

Boundary or saved-state stack
- Store exactly what must be restored later, such as an index or (previousState, repeatCount).
- Push when a new unresolved boundary or nested context begins.
- Pop when the matching input closes that context, then combine it with the current state.
- Use a sentinel such as -1 when lengths are measured from the boundary before the first element.
Parallel metadata stack
- Push one metadata entry whenever a value is pushed.
- Derive the new metadata from the incoming value and the previous metadata top.
- Pop both stacks together so their depths always match.
Expression stack
- Build the current number one digit at a time.
- When an operator or closing parenthesis is reached, apply the previous operator.
- Push positive or negative terms for + and -; immediately combine the stack top for * and /.
- Recursively evaluate parentheses and use the returned value as the current number.
Monotonic stack
- Store (value, index) pairs when comparisons need the value and answers need a distance or position.
- Pop while the current value violates the required increasing or decreasing order.
- Resolve each popped entry using the current index and the new stack top.
- Push the current pair, then explicitly handle entries that never encounter a boundary.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class MonotonicStackTemplate {
	public static int[] nextGreater(int[] values) {
		int N = values.length;
		int[] res = new int[N];
		Arrays.fill(res, -1);
		Deque<int[]> stack = new ArrayDeque<>(); // {value, index}

		for (int index = 0; index < N; index++) {
			int value = values[index];
			while (!stack.isEmpty() &&
				stack.peek()[0] < value) {
				int[] previous = stack.pop();
				int previousIndex = previous[1];
				res[previousIndex] = value;
			}
			stack.push(new int[] {value, index});
		}

		return res;
	}
}

def next_greater(values: list[int]) -> list[int]:
    N = len(values)
    res = [-1] * N
    stack = [] # (value, index)

    for index, value in enumerate(values):
        while stack and stack[-1][0] < value:
            _, previous_index = stack.pop()
            res[previous_index] = value
        stack.append((value, index))

    return res

Problems

32. Longest Valid Parentheses

Keep indices in a stack and initialize it with -1, the boundary before the string begins. Push the index of every (. For each ), pop once; if the stack becomes empty, store the current index as the new boundary, otherwise the distance from the current index to the stack’s top is the length of a valid substring. This takes O(n) time and O(n) space.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int longestValidParentheses(String s) {
		Deque<Integer> stack = new ArrayDeque<>();
		stack.push(-1);
		int res = 0;

		for (int i = 0; i < s.length(); i++) {
			char character = s.charAt(i);

			if (character == '(') {
				stack.push(i);
			} else {
				stack.pop();
				if (stack.isEmpty()) {
					stack.push(i);
				} else {
					res = Math.max(res, i - stack.peek());
				}
			}
		}

		return res;
	}
}

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        res = 0

        for i, character in enumerate(s):
            if character == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    res = max(res, i - stack[-1])

        return res

155. Min Stack

Design a stack whose minimum query is constant time. Keep the values in stack and the minimum at every corresponding depth in min_stack. Pushing adds to both stacks, and popping from both automatically restores the previous minimum.

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
	private final Deque<Integer> stack;
	private final Deque<Integer> minStack;

	public MinStack() {
		stack = new ArrayDeque<>();
		minStack = new ArrayDeque<>();
	}

	public void push(int value) {
		stack.push(value);
		if (minStack.isEmpty()) {
			minStack.push(value);
		} else {
			minStack.push(Math.min(value, minStack.peek()));
		}
	}

	public void pop() {
		stack.pop();
		minStack.pop();
	}

	public int top() {
		return stack.peek();
	}

	public int getMin() {
		return minStack.peek();
	}
}

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, value: int) -> None:
        self.stack.append(value)
        if len(self.min_stack) == 0:
            self.min_stack.append(value)
        else:
            self.min_stack.append(min(value, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

394. Decode String

Decode nested expressions such as 3[a2[c]]. On [, push the current string and repeat count together. On ], pop that state, restore the outer string, and append the decoded inner segment the stored number of times.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	private static class Frame {
		String prevStr;
		int prevNum;

		Frame(String prevStr, int prevNum) {
			this.prevStr = prevStr;
			this.prevNum = prevNum;
		}
	}

	public String decodeString(String s) {
		Deque<Frame> stack = new ArrayDeque<>();
		int num = 0;
		StringBuilder curr = new StringBuilder();

		for (char character : s.toCharArray()) {
			if (Character.isDigit(character)) {
				num = num * 10 + character - '0';
			} else if (character == '[') {
				stack.push(new Frame(curr.toString(), num));
				num = 0;
				curr = new StringBuilder();
			} else if (character == ']') {
				Frame frame = stack.pop();
				String decoded = curr.toString();
				curr = new StringBuilder(frame.prevStr);

				for (int i = 0; i < frame.prevNum; i++) {
					curr.append(decoded);
				}
			} else {
				curr.append(character);
			}
		}

		return curr.toString();
	}
}

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        num = 0
        curr = ""

        for char in s:
            if char.isdigit():
                num = num * 10 + int(char)
            elif char == "[":
                stack.append((curr, num))
                num = 0
                curr = ""
            elif char == "]":
                prev_str, prev_num = stack.pop()
                curr = prev_str + prev_num * curr
            else:
                curr += char

        return curr

772. Basic Calculator III

Evaluate each parenthesized expression with a recursive helper that returns both its value and the index of its closing parenthesis. Each call uses a local stack to enforce precedence: addition and subtraction push signed values, while multiplication and division immediately combine with the stack’s top. Java integer division and Python’s int(a / b) both truncate toward zero. Each character is processed once, so the solution takes O(n) time and O(n) space.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int calculate(String s) {
		return helper(s, 0)[0];
	}

	private int[] helper(String s, int idx) {
		Deque<Integer> stack = new ArrayDeque<>();
		int num = 0;
		char op = '+';

		while (idx < s.length()) {
			char character = s.charAt(idx);

			if (Character.isDigit(character)) {
				num = num * 10 + character - '0';
			} else if (character == '+' || character == '-' ||
				character == '*' || character == '/') {
				calc(stack, op, num);
				op = character;
				num = 0;
			} else if (character == '(') {
				int[] nested = helper(s, idx + 1);
				num = nested[0];
				idx = nested[1];
			} else if (character == ')') {
				calc(stack, op, num);
				return new int[] {sum(stack), idx};
			}

			idx++;
		}

		calc(stack, op, num);
		return new int[] {sum(stack), idx};
	}

	private void calc(Deque<Integer> stack, char op, int num) {
		if (op == '+') {
			stack.push(num);
		} else if (op == '-') {
			stack.push(-num);
		} else if (op == '*') {
			stack.push(stack.pop() * num);
		} else if (op == '/') {
			stack.push(stack.pop() / num);
		}
	}

	private int sum(Deque<Integer> stack) {
		int res = 0;
		for (int value : stack) {
			res += value;
		}
		return res;
	}
}

class Solution:
    def calculate(self, s: str) -> int:
        def helper(idx):
            stack = []
            num = 0
            op = '+'

            def calc(op, num):
                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))

            while idx < len(s):
                char = s[idx]

                if char.isdigit():
                    num = num * 10 + int(char)

                elif char in '+-*/':
                    calc(op, num)
                    op = char
                    num = 0

                elif char == '(':
                    num, idx = helper(idx + 1)

                elif char == ')':
                    calc(op, num)
                    return sum(stack), idx

                idx += 1

            calc(op, num)
            return sum(stack), idx

        result, _ = helper(0)
        return result

503. Next Greater Element II

Use a decreasing stack of [value, index] pairs. Scan the array twice and read values with nums[index % n]; the second pass lets values near the beginning resolve elements near the end. When the current value is greater than the stack’s top, pop that pair and write the answer at previousIndex % n. The two passes still take O(n) time and O(n) space.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
	public int[] nextGreaterElements(int[] nums) {
		int N = nums.length;
		int[] res = new int[N];
		Arrays.fill(res, -1);
		Deque<int[]> stack = new ArrayDeque<>(); // [num, idx]

		// should have a mono-decreasing stack [4, 3, 2, etc.]
		// later larger element can pop that stack
		for (int idx = 0; idx < 2 * N; idx++) {
			int num = nums[idx % N];

			while (!stack.isEmpty() &&
				stack.peek()[0] < num) {
				int[] previous = stack.pop();
				int prevIdx = previous[1];
				res[prevIdx % N] = num;
			}

			stack.push(new int[] {num, idx});
		}

		return res;
	}
}

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        res = [-1] * N
        stack = [] # [num, idx]

        # should have a mono-descreasing stack [4, 3, 2, etc.]
        # later larger element can pop that stack
        for idx in range(2*N):
            num = nums[idx % N]
            while stack and stack[-1][0] < num:
                _, prev_idx = stack.pop()
                res[prev_idx % N] = num
            stack.append([num, idx])

        return res

739. Daily Temperatures

For each day, find how many days pass before a warmer temperature. Keep unresolved (temperature, index) pairs in a decreasing stack. A warmer current day pops every smaller temperature and uses the two indices to calculate the wait.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int[] dailyTemperatures(int[] temperatures) {
		// mono-decreasing stack
		int N = temperatures.length;
		Deque<int[]> stack = new ArrayDeque<>(); // {temp, idx}
		int[] res = new int[N];

		for (int idx = 0; idx < N; idx++) {
			int temp = temperatures[idx];
			while (!stack.isEmpty() &&
				temp > stack.peek()[0]) {
				int[] previous = stack.pop();
				int prevIdx = previous[1];
				res[prevIdx] = idx - prevIdx;
			}
			stack.push(new int[] {temp, idx});
		}

		return res;
	}
}

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # mono-decreasing stack
        N = len(temperatures)
        stack = [] # (temp, idx) tuple
        res = [0] * N

        for idx, temp in enumerate(temperatures):
            while stack and temp > stack[-1][0]:
                prev_temp, prev_idx = stack.pop()
                res[prev_idx] = idx - prev_idx
            stack.append((temp, idx))

        return res

84. Largest Rectangle in Histogram

Find the largest rectangle formed by consecutive bars. Keep increasing (height, index) pairs above a (0, -1) sentinel. When a shorter bar arrives, it becomes the right boundary for every taller popped bar, while the new stack top supplies the left boundary. After the scan, explicitly pop the remaining bars and use the end of the histogram as their right boundary.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int largestRectangleArea(int[] heights) {
		// mono-increase stack stores {height, idx}
		Deque<int[]> stack = new ArrayDeque<>();
		stack.push(new int[] {0, -1});
		int res = 0;

		for (int idx = 0; idx < heights.length; idx++) {
			int height = heights[idx];

			while (!stack.isEmpty() &&
				height < stack.peek()[0]) {
				int[] previous = stack.pop();
				int prevHeight = previous[0];
				int prevIdx = previous[1];
				int width = idx - stack.peek()[1] - 1;
				res = Math.max(res, width * prevHeight);
			}

			stack.push(new int[] {height, idx});
		}

		while (stack.size() > 1) {
			int[] previous = stack.pop();
			int prevHeight = previous[0];
			int prevIdx = previous[1];
			int width = heights.length - stack.peek()[1] - 1;
			res = Math.max(res, width * prevHeight);
		}

		return res;
	}
}

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # mono-increase stack stores (height, idx)
        stack = [(0, -1)]
        res = 0

        for idx, height in enumerate(heights):
            while stack and height < stack[-1][0]:
                prev_height, prev_idx = stack.pop()
                width = idx - stack[-1][1] - 1
                res = max(res, width * prev_height)

            stack.append((height, idx))

        while len(stack) > 1:
            prev_height, prev_idx = stack.pop()
            width = len(heights) - stack[-1][1] - 1
            res = max(res, width * prev_height)

        return res