# LU.5 Monotonic Stack

> A stack kept in sorted (decreasing) order answers "next greater element" and "how far away is it" for every index in one O(n) pass.

Chapter: Level Up: Problem Patterns · ~50 min · hard · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/monotonic-stack

## Mental model

People stand in a line, all looking right. For each person, who is the **first taller person** they can see?

Walk the line left to right with a **stack of people still waiting** for a taller person. Keep it **decreasing**: tallest at the bottom. When a new person arrives, every shorter person at the top of the stack has just found their answer: **pop** them and record it. Then push the newcomer.

```cpp
while (!st.empty() && a[st.top()] < a[i]) {
    ans[st.top()] = a[i];          // next greater
    span[st.top()] = i - st.top(); // how far away
    st.pop();
}
st.push(i);
```

Each index is pushed once and popped at most once, so the whole thing is **O(n)**.

- **Equal values**: with `<`, an equal height does not count as taller. Use `<=` if it should.
- **Circular arrays**: loop `i` from 0 to 2n − 1 and use `i % n`, pushing only during the first lap.
- **Store indices**, not values, so you can compute distances.

Also see the **LeetCode monotonic problems**: Car Fleet, Remove K Digits, Sum of Subarray Minimums, 132 Pattern, Shortest Subarray with Sum ≥ K (monotonic **queue**).

> Built on Chapter 5 (stacks). Not on the exam.

## C++ code: monotonic-stack.cpp

```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                                    // indices; values decreasing
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {   // a[i] answers everyone smaller
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

vector<int> waitDays(const vector<int>& a) {          // span: how far away is the next greater?
    vector<int> d(a.size(), 0);
    stack<int> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!st.empty() && a[st.top()] < a[i]) { d[st.top()] = i - st.top(); st.pop(); }
        st.push(i);
    }
    return d;
}

vector<int> nextGreaterCircular(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;
    for (int i = 0; i < 2 * n; i++) {                 // loop twice to wrap around
        while (!st.empty() && a[st.top()] < a[i % n]) { ans[st.top()] = a[i % n]; st.pop(); }
        if (i < n) st.push(i);
    }
    return ans;
}

void print(const char* label, const vector<int>& v) {
    cout << label;
    for (int x : v) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<int> a = {2, 1, 3, 5, 6, 1};
    print("a:                ", a);
    print("next greater:     ", nextGreater(a));
    print("span (j - i):     ", waitDays(a));
    print("circular greater: ", nextGreaterCircular(a));
}
```

Expected output:

```text
a:                2 1 3 5 6 1 
next greater:     3 3 5 6 -1 -1 
span (j - i):     2 1 1 1 0 0 
circular greater: 3 3 5 6 -1 2
```

## Complexity

| Case | Cost |
| --- | --- |
| brute force (scan right from each i) | O(n²) |
| monotonic stack | O(n): each index pushed and popped once |

Space: O(n)

Pop on `<` and equal values do **not** answer each other; pop on `<=` and they do. For circular arrays, loop **twice** (i from 0 to 2n − 1, index i % n), pushing only in the first lap.

## Videos

- [Monotonic Stack Data Structure Explained](https://youtu.be/Dq_ObZwTY_Q) (AlgoMonster): The data structure itself, explained in under 6 minutes.
- [Daily Temperatures: Monotonic Stack](https://youtu.be/cTBiBSnjO3c) (NeetCode): NeetCode's Daily Temperatures, the span version of this page.

## Exam lens

Likely questions:

- Why is the monotonic stack O(n) despite the nested while loop?
- How does the answer change if you pop on `<=` instead of `<`?
- How do you handle a circular array?

Common mistakes:

- Storing values instead of indices, which loses the span (distance).
- Pushing during the second lap of a circular array.
- Forgetting that items left on the stack at the end have no answer (−1).

## Quick check

1. `2 1 3 5 6 1`: next greater element of index 1 (value 1)?
   A. 2
   B. 3
   C. 5
   D. -1
   Answer: B. The first bigger value to its right is 3.

2. Span (distance) for index 0 (value 2)?
   A. 1
   B. 2
   C. 3
   D. 0
   Answer: B. 3 is at index 2, which is 2 − 0 = 2 steps away.

3. Circular version: next greater for the last 1?
   A. -1
   B. 2
   C. 3
   D. 6
   Answer: B. Wrapping around, the first bigger value is the 2 at index 0.

## Practice

**Trace by hand.** Run next-greater on `2 1 3 5 6 1`. Write the stack (as values) after each i.

Solution:

- i0: `[2]` · i1: `[2 1]`
- i2: 3 pops 1 (ans 3) and 2 (ans 3) → `[3]`
- i3: pops 3 (ans 5) → `[5]` · i4: pops 5 (ans 6) → `[6]`
- i5: `[6 1]`, leftovers get −1

Answer: `3 3 5 6 -1 -1`, spans `2 1 1 1 0 0`.


**Implement it.** Compute the **previous smaller** element for every index.

Hint: Scan left to right with an increasing stack. Pop while the top is ≥ a[i]; the top that remains (if any) is the answer.

**Problems:**

- [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) (medium). Hint: This page's span version.
- [Car Fleet](https://leetcode.com/problems/car-fleet/) (medium). Hint: Sort by position descending; keep a stack of arrival times; a slower car ahead absorbs the faster ones behind.
- [Remove K Digits](https://leetcode.com/problems/remove-k-digits/) (medium). Hint: Increasing stack of digits. Pop a bigger digit while k > 0.
- [Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/) (medium). Hint: For each i, find how far it is the minimum to the left and right (previous/next smaller). Use `<` on one side and `<=` on the other to avoid double counting.

## Mastery checklist

- [ ] I can run a monotonic stack by hand.
- [ ] I can compute next greater and its distance.
- [ ] I can handle equal values and circular arrays.