---
title: "Monotonic Stack"
description: "Keep stack values ordered and pop smaller candidates to find each element's next greater value."
source: https://vizlearn.app/algorithms/data-structures/monotonic-stack
---

# Monotonic Stack

A **monotonic stack** solves “nearest greater or smaller” queries in one scan by keeping only candidates that can still matter. This lesson uses a decreasing stack for **Next Greater Element**: for every index, find the first strictly larger value to its right, in O(n) time and O(n) auxiliary space.

The surprising part is the nested `while` loop. It looks like a recipe for quadratic work, but it is not. Every index enters the stack once and can leave it only once. Across the entire scan there are exactly n pushes and at most n pops, so the total stack work is at most `2n`.

## How a Monotonic Stack Works

The stack stores **indices**, not only values. Keeping an index gives us both pieces of information we need: `nums[index]` for comparisons and `answer[index]` for writing the result later.

For the decreasing version, values are non-increasing from bottom to top. When we inspect a new value `nums[i]`, we repeatedly compare it with the value at the stack top:

```python
while stack and nums[stack[-1]] < nums[i]:
    j = stack.pop()
    answer[j] = nums[i]
stack.append(i)
```

If the top value is smaller, the current value is its next greater element. Why can we be certain it is the **first** greater value to the right? That index has stayed on the stack through every position between it and `i`. None of those earlier positions was large enough to pop it. The current value is the first one that is.

The comparison is deliberately strict: `nums[top] < nums[i]`. Equal values do not resolve each other because “next greater” means greater, not greater-or-equal.

## When to Use a Monotonic Stack

Look for this pattern: each position asks for the **nearest greater or smaller value on one side**. A monotonic stack can often replace a repeated outward search with one scan.

Typical applications include:

- **Daily Temperatures:** find how far ahead a warmer day appears.
- **Stock Span:** find the previous greater boundary for each price.
- **Largest Rectangle in Histogram:** find the nearest smaller boundary on both sides of each bar.

Store indices when the result needs more than the matching value. The same stack can return a value, an index, or a distance by changing only what gets written when an index is popped.

## Monotonic Stack Step by Step

The default input is:

```text
nums = [2, 1, 5, 3, 4]
```

The answer starts as `[-1, -1, -1, -1, -1]`. A `-1` remains wherever no greater value appears to the right.

1. **i = 0, current = 2.** The stack is empty, so push index 0. Stack values: `[2]`.
2. **i = 1, current = 1.** Compare top 2 with current 1. `2 < 1` is false, so nothing pops. Push index 1. Stack values: `[2, 1]`.
3. **i = 2, current = 5.** Compare top 1 with 5. The guard is true, so pop index 1 and write `answer[1] = 5`.
4. The same current value 5 checks the new top 2. `2 < 5` is also true, so pop index 0 and write `answer[0] = 5`.
5. The stack is now empty. Push index 2. Stack values: `[5]`.
6. **i = 3, current = 3.** `5 < 3` is false. Push index 3. Stack values: `[5, 3]`.
7. **i = 4, current = 4.** `3 < 4` is true. Pop index 3 and write `answer[3] = 4`.
8. Check the new top. `5 < 4` is false, so stop popping and push index 4. Stack values: `[5, 4]`.
9. The scan ends. Indices 2 and 4 never found a greater value on their right, so their `-1` sentinels remain.

The final result is:

```text
answer = [5, 5, -1, 4, -1]
```

The animation deliberately splits a successful loop iteration into separate **compare → pop → resolve** beats. That separation makes the state provenance explicit: the stack changes on the pop beat, and the answer array changes on the resolve beat.

## Why the Nested Loop Is O(n)

| Case | Time | Space |
|---|---|---|
| All | O(n) | O(n) |

The time complexity is linear even though a `while` sits inside the `for`. Suppose an input has n elements. Each index is pushed exactly once when its turn arrives. An index that is popped disappears permanently and can never be popped again.

Therefore:

- pushes = n,
- pops ≤ n,
- pushes + pops ≤ `2n`.

The inner `while` can run several times for one current value, as 5 does in the default example, but those extra iterations consume stack entries that will never return. This is an **amortized analysis**: some iterations are expensive, but the total work over all iterations is linear.

The auxiliary stack can grow to n indices. A strictly decreasing input such as `[6, 5, 4, 3, 2, 1]` never pops during the scan, so O(n) extra space is the real worst case.

## Edge Cases

### Strictly increasing values

For `[1, 2, 3, 4, 5]`, every new value pops the previous top. The stack stays shallow and the result is `[2, 3, 4, 5, -1]`.

### Strictly decreasing values

For `[5, 4, 3, 2, 1]`, no current value is greater than the top. Nothing pops, every index remains on the stack, and every answer is `-1`. This is the maximum-stack-space case.

### Duplicate values

With values such as `[2, 2, 3]`, the second 2 does **not** pop the first 2 because `2 < 2` is false. When 3 arrives, it pops both 2s in turn, producing `[3, 3, -1]`.

### No greater value to the right

Remaining stack entries are not an error. They simply never encountered a greater value, so the initialized `-1` answer is already correct.

## Common Mistakes

### Replacing `while` with `if`

This is the most important bug. On the default stack `[2, 1]` with current value 5, one `if` pops only 1. Index 0, whose value is 2, would incorrectly remain unresolved even though 5 is also its first greater value. The algorithm needs repeated pops.

### Using `<=` instead of `<`

That silently changes the problem from “next strictly greater” to a greater-or-equal variant. Equal values would start resolving each other.

### Storing values when the answer needs indices

A stack of raw values can tell you what to compare, but not which position in `answer` to update. Storing indices preserves both the value lookup and the destination slot.

### Calling the stack “strictly decreasing”

With the strict `<` guard, duplicates may coexist. The precise invariant is **non-increasing from bottom to top**. If all input values are distinct, it happens to be strictly decreasing.

### Looking at the nested loop and declaring O(n²)

Count object lifetimes, not indentation. An index is pushed once and popped at most once. The final lifetime row and work meter expose exactly that accounting.