Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Monotonic Stack

Keep candidates in order so each element resolves its answer once.

time O(n)space O(n)

What it is

Maintain a stack whose values are monotone. When a new element breaks the order, pop and resolve the popped ones. Every element is pushed and popped once, so the total is O(n).

When to reach for it

  • Next greater or smaller element
  • Span, temperature or histogram problems
  • Matching nested structure

Clues in the problem

  • For each i, look right or left for the first element that is bigger or smaller
  • Brute force is an inner loop that scans forward

Template

def next_greater(a):
res = [-1] * len(a)
st = [] # indices, values decreasing
for i, x in enumerate(a):
while st and a[st[-1]] < x:
res[st.pop()] = x
st.append(i)
return res

Practice problems

  • Daily Temperatures
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Trapping Rain Water

Common mistakes

  • Storing values when you need indices
  • Wrong comparison direction (strict vs non-strict) with duplicates
  • Forgetting to drain the stack at the end when needed