Stack-Based Problem Solving Patterns: 5 Essential Techniques from the LeetCode Repository

The most effective stack-based problem solving patterns include monotonic stacks for nearest greater/smaller elements, explicit stack implementations for iterative tree traversals and graph DFS, validation stacks for parentheses matching, and augmented stacks with lazy propagation for custom operations like increment.

Mastering stack-based problem solving patterns is essential for efficiently tackling algorithmic challenges involving nested structures, nearest neighbors, and depth-first exploration. The open-source repository azl397985856/leetcode documents five battle-tested patterns that transform complex problems into simple push-and-pop decisions. These techniques leverage the LIFO (last-in-first-out) property to achieve optimal time complexity while avoiding recursion limits.

1. Monotonic Stack Pattern

The monotonic stack maintains elements in strictly increasing or decreasing order to solve "next greater element" and "nearest smaller" problems efficiently.

When to Apply Monotonic Stacks

Use this pattern for Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water. The core insight is that when a new element breaks the monotonicity, it becomes the answer for all popped elements.

Implementation Details

As documented in thinkings/monotone-stack.md, the algorithm scans the array while maintaining a stack of indices. When current_element > arr[stack.top], the current index represents the next greater element for the popped position.

def next_greater(nums):
    stack = []               # holds indices

    ans = [-1] * len(nums)   # default: no greater element

    for i, x in enumerate(nums):
        while stack and x > nums[stack[-1]]:
            idx = stack.pop()
            ans[idx] = x
        stack.append(i)
    return ans

The JavaScript implementation follows the same logic:

function nextGreater(arr) {
    const stack = [];               // indices
    const res = new Array(arr.length).fill(-1);
    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
            const idx = stack.pop();
            res[idx] = arr[i];
        }
        stack.push(i);
    }
    return res;
}

Both implementations achieve O(N) time complexity because each element is pushed and popped exactly once.

2. Iterative Tree Traversal with Explicit Stack

Recursion implicitly uses the call stack, but converting to an explicit stack prevents stack overflow and provides fine-grained control over traversal order.

The Color-Marking Technique

As detailed in thinkings/tree.md, the unified color-marking approach uses tuples of (state, node) where WHITE indicates the node needs processing and GRAY indicates it has been visited.

def inorder(root):
    WHITE, GRAY = 0, 1
    stack = [(WHITE, root)]
    result = []
    while stack:
        color, node = stack.pop()
        if not node:
            continue
        if color == WHITE:
            # Post-order: left -> right -> node

            stack.append((GRAY, node))
            stack.append((WHITE, node.right))
            stack.append((WHITE, node.left))
        else:
            result.append(node.val)
    return result

This pattern generalizes to preorder and inorder by simply reordering the push operations, eliminating recursion depth limits while maintaining O(N) time and O(H) space complexity, where H is the tree height.

3. Explicit Search Stack for Graph DFS

For large graphs or environments without tail-call optimization, an explicit search stack implements depth-first search without recursion limits.

Implementation Strategy

According to thinkings/search.md, the pattern initializes the stack with the start vertex, then repeatedly pops vertices, marks them visited, and pushes unvisited neighbors until exhaustion.

def dfs(start, adj):
    visited, order = set(), []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        # Reverse iteration to mimic recursion order

        for v in reversed(adj[u]):
            if v not in visited:
                stack.append(v)
    return order

This approach guarantees O(V + E) time complexity while using O(V) space for the explicit stack and visited set, making it suitable for graphs with deep traversal paths that would overflow the recursive call stack.

4. Stack-Based Validation Patterns

Validation stacks verify well-formedness of nested structures by pushing opening symbols and popping when encountering matching closing symbols.

Parentheses Matching and Sequence Validation

The classic application checks that every opening bracket has a corresponding closing bracket in the correct order. When a closing symbol appears, it must match the stack's top; otherwise, the sequence is invalid.

This pattern also applies to Validate Stack Sequences problems, where you simulate push/pop operations to verify if a given sequence is achievable with a single stack. As referenced in thinkings/monotone-stack.md, you push elements from the pushed array onto a stack, and whenever the top matches the current element in the popped array, you pop it. Successfully consuming the entire popped array confirms the sequence is valid.

5. Design Pattern: Augmented Stacks with Lazy Propagation

Custom stack designs support additional operations like incrementing the bottom k elements while maintaining O(1) time complexity for standard operations.

The Increment Stack Technique

As referenced in the repository's thinkings/monotone-stack.md, the solution stores an auxiliary increment array where inc[i] records the cumulative increment to be applied to the first i elements. When popping, the pending increment transfers to the next element, preserving constant-time updates.

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.inc = [0] * (maxSize + 1)  # 1-indexed for convenience

        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) -> int:
        if not self.stack:
            return -1
        idx = len(self.stack) - 1
        # Apply accumulated increment

        if idx > 0:
            self.inc[idx - 1] += self.inc[idx]
        val = self.stack.pop() + self.inc[idx]
        self.inc[idx] = 0  # reset for future use

        return val

    def increment(self, k: int, val: int) -> None:
        idx = min(k, len(self.stack)) - 1
        if idx >= 0:
            self.inc[idx] += val

This design achieves O(1) time for push, pop, and increment operations.

Key Files in the Repository

The azl397985856/leetcode repository organizes these patterns into dedicated documentation files:

File	Purpose
thinkings/monotone-stack.md	Detailed explanation of monotonic stacks, next greater element algorithms, and custom stack designs like the increment operation.
thinkings/tree.md	Iterative traversal techniques using explicit stacks, including the color-marking method for unified preorder, inorder, and postorder walks.
thinkings/search.md	Stack-based depth-first search implementations for graphs, avoiding recursion limits.
thinkings/stack.md	General stack fundamentals and validation patterns (parentheses matching, sequence validation).

These files form a comprehensive knowledge base for stack-based problem solving patterns within the LeetCode collection.

Summary

• Monotonic stacks solve nearest greater/smaller element problems in O(N) time by maintaining sorted order and popping when monotonicity breaks.
• Explicit stack DFS replaces recursion for trees and graphs, preventing stack overflow and providing fine-grained traversal control via color-marking or neighbor iteration.
• Validation stacks verify well-formedness of nested structures and simulate stack sequences by matching pushes and pops.
• Augmented stacks with lazy propagation support custom operations like increment(k, val) in O(1) time using auxiliary arrays.

Frequently Asked Questions

What is a monotonic stack and when should I use it?

A monotonic stack maintains elements in strictly increasing or decreasing order. Use it for problems requiring the next greater element, next smaller element, largest rectangle in histogram, or trapping rain water. When a new element violates the monotonic property, you pop elements from the stack—the current element becomes their "next greater" answer.

How do I convert a recursive tree traversal to an iterative stack approach?

Replace the implicit call stack with an explicit stack of tuples containing (state, node). Use a color-marking technique where WHITE means "to visit" and GRAY means "processed". Push the node with WHITE, then push its children with WHITE in reverse order, followed by the node itself with GRAY. When you pop a GRAY node, add its value to your result. This pattern appears in thinkings/tree.md.

Why use an explicit stack for graph DFS instead of recursion?

Explicit stacks prevent stack overflow when recursion depth exceeds language limits (often around 1000-10000 frames). They also allow you to control memory usage precisely and implement iterative deepening or custom traversal orders more easily. As documented in thinkings/search.md, the pattern initializes the stack with the start vertex, then pops, marks visited, and pushes unvisited neighbors until exhaustion.

Can stack patterns solve validation problems like parentheses matching?

Yes, validation stacks are the standard solution for checking well-formedness. Push every opening bracket onto the stack; when encountering a closing bracket, verify it matches the stack's top. If the stack is empty or the top doesn't match, the sequence is invalid. This pattern also applies to Validate Stack Sequences problems, where you simulate push/pop operations to verify if a given sequence is achievable with a single stack.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}