# Monotonic Stack — Next Greater Element, Stock Span and Histograms in O(n)

Source: https://skills101.in/learn/dsa/dsa-monotonic-stack — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

Many array problems ask, for **every** element: "what is the **next bigger** value to my right?" (or the previous smaller one, or how far away it is). Checking every pair is O(n²). A **monotonic stack** — a stack whose values are always kept in increasing or decreasing order — answers all of them in **one pass, O(n)**.

## 1. Next greater element

**Problem:** for each element, print the first value to its **right** that is **strictly greater**, or `-1` if there is none.

**Idea:** walk left to right and keep a stack of elements that are **still waiting** for their next greater value. When a new value `x` arrives, it is the answer for every waiting element smaller than it — pop them all. Then `x` waits too.

![For the array 2 1 4 3 6 5 the next greater elements are 4 4 6 6 -1 -1; arrows go from 2 and 1 to 4, and from 4 and 3 to 6](https://skills101.in/learn-img/dsa/next-greater.svg)

The waiting elements always form a **decreasing** stack — anything smaller than a newer element would already have been popped.

![Stack after each step: see 2 gives [2]; see 1 gives [2, 1]; see 4 pops 1 and 2 and gives [4]; see 3 gives [4, 3]; see 6 pops 3 and 4 and gives [6]; see 5 gives [6, 5]](https://skills101.in/learn-img/dsa/stack-trace.svg)

```python
def next_greater(a):
    ans = [-1] * len(a)
    stack = []                       # indexes still waiting for an answer
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            ans[stack.pop()] = x     # x is the next greater for that index
        stack.append(i)
    return ans

print(next_greater([2, 1, 4, 3, 6, 5]))
print(next_greater([5, 4, 3]))
```

```text
[4, 4, 6, 6, -1, -1]
[-1, -1, -1]
```

**Why O(n)?** Each index is pushed **once** and popped **at most once**, so the inner `while` runs at most n times in total — even though it is inside a `for`.

**Store indexes, not values.** With the index you can return the value, the **distance** (`i − j`) or the position — whatever the problem asks.

## 2. The four variants

Change two things — the **comparison** and the **direction** — and the same loop solves four problems:

| You want | Walk | Pop while the top is… | The stack is |
|---|---|---|---|
| next **greater** | left → right | **smaller** than x | decreasing |
| next **smaller** | left → right | **greater** than x | increasing |
| previous **greater** | left → right | ≤ x, then the top is the answer | decreasing |
| previous **smaller** | left → right | ≥ x, then the top is the answer | increasing |

For the "previous" versions, the answer for `x` is whatever is left on top **after** popping.

```python
def previous_smaller(a):
    ans, stack = [], []
    for x in a:
        while stack and stack[-1] >= x:
            stack.pop()
        ans.append(stack[-1] if stack else -1)
        stack.append(x)
    return ans

print(previous_smaller([4, 5, 2, 10, 8]))
```

```text
[-1, 4, -1, 2, 2]
```

## 3. Daily temperatures (distance to the next warmer day)

"For each day, how many days until a warmer one? 0 if never." Same loop; store the **distance**.

```python
def daily_temperatures(t):
    ans, stack = [0] * len(t), []
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
```

```text
[1, 1, 4, 2, 1, 1, 0, 0]
```

## 4. Largest rectangle in a histogram

The hardest classic. Each bar can be the **shortest bar** of a rectangle that stretches left and right until a **shorter** bar blocks it. So for each bar we need its previous smaller and next smaller bar — one increasing stack finds both: when a bar is popped, the bar that pops it is its next smaller, and the bar below it on the stack is its previous smaller.

```python
def largest_rectangle(h):
    stack, best = [], 0               # indexes, heights increasing
    for i, x in enumerate(h + [0]):   # a final 0 pops everything left
        while stack and h[stack[-1]] > x:
            height = h[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))
```

```text
10
4
```

The answer 10 is the rectangle of height 5 over the bars `5, 6`. The sentinel `0` at the end makes sure every bar is popped and measured.

### Next greater element in Java

```java
import java.util.*;

public class Main {
    static int[] nextGreater(int[] a) {
        int[] ans = new int[a.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();   // use ArrayDeque, not the old Stack class
        for (int i = 0; i < a.length; i++) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                ans[stack.pop()] = a[i];
            }
            stack.push(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{2, 1, 4, 3, 6, 5})));
    }
}
```

```text
[4, 4, 6, 6, -1, -1]
```

## 5. How to spot a monotonic stack problem

- The words **next / previous greater / smaller**, "how many days until", "span", "visible", "nearest taller".
- A brute force with a nested loop that scans left or right **until** it finds something bigger or smaller.
- Circular arrays (next greater element II): loop over the array **twice** (`i % n`), pushing only during the first pass.

## Common mistakes

- Pushing values when you later need positions or distances — push **indexes**.
- Using `<=` instead of `<` (or the other way round): it decides whether **equal** values count as "greater". Read the problem.
- Forgetting the sentinel (or a final clean-up loop) in the histogram problem, so bars left on the stack are never measured.
- Thinking the nested `while` makes it O(n²) — it doesn't; count pushes and pops.

## Quick recap

- A monotonic stack keeps values in order; elements wait on it until their answer arrives.
- Next greater: pop while the top is smaller than `x`; each popped index gets `x`.
- Every index is pushed and popped at most once: **O(n)** time, O(n) space.
- Same pattern: next/previous smaller, daily temperatures, stock span, largest rectangle.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-monotonic-stack