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:

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:

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:

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)

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.