Stacks and monotonic stacks

Remember unresolved candidates.

Understand the problem

A monotonic stack stores indices whose answer has not yet been found. On a larger value, pop smaller unresolved values and calculate their distance to the current index.

Trade-offs and pitfalls

Nested loops can still be O(n) when total pushes and pops are bounded.

Check your understanding

Explain why indices are more useful than just values.

Your study notes