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

> Discover 5 essential stack-based problem solving patterns including monotonic stacks, iterative traversals, and parentheses matching. Enhance your algorithm skills with these LeetCode techniques.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: best-practices
- Published: 2026-03-06

---

**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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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:

```javascript
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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/monotone-stack.md) | Detailed explanation of monotonic stacks, next greater element algorithms, and custom stack designs like the increment operation. |
| [`thinkings/tree.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/tree.md) | Iterative traversal techniques using explicit stacks, including the color-marking method for unified preorder, inorder, and postorder walks. |
| [`thinkings/search.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/search.md) | Stack-based depth-first search implementations for graphs, avoiding recursion limits. |
| [`thinkings/stack.md`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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.