# Stacks and Monotonic Stacks — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/b-stack

> Resolve items when their answer arrives.

## Matching and next greater element

A stack (Python list with `append`/`pop`) handles nested structure: matching brackets, evaluating expressions, undo history. A **monotonic stack** keeps indices with decreasing (or increasing) values; when a larger value arrives, it resolves every smaller pending index at once. This solves "next greater element", "daily temperatures", stock spans and the largest rectangle in a histogram in O(n).

## Daily temperatures and valid brackets, run

I ran this with Python 3.12.3 (standard library only). Each day gets the number of days until a warmer one (0 if none); bracket validation fails for wrong nesting and unclosed brackets.

```python
# Monotonic stack: days until a warmer temperature
def daily_temperatures(temps):
    res, stack = [0] * len(temps), []    # stack of indices with decreasing temps
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

# Valid parentheses with a plain stack
def valid(s):
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print([valid(s) for s in ("()[]{}", "([)]", "{[]}", "((")])
```

Output:

```
[1, 1, 4, 2, 1, 1, 0, 0]
[True, False, True, False]
```

## Check the empty stack

Popping an empty stack is the classic bug; handle a closing bracket with nothing open.

**Quiz:** Which pattern finds the next greater element for every position in O(n)?

- [ ] A min-heap
- [x] A monotonic stack
- [ ] Binary search on each element
- [ ] Sorting the array

*Answer:* A monotonic stack. Pending items resolve together.