Monotonic stacks

What is a stack?

A stack is a collection where you add and remove from the same end, called the top. Push means add an item; pop means remove the top item; peek means read the top without removing it. The last item added is the first removed. This order is called last in, first out, or LIFO.

Example: Push 4, then 8, then 15. The next pop returns 15. After that, the top is 8.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays

Understand the idea

A monotonic stack keeps values in one order and represents unresolved candidates. Incoming values pop candidates whose answers they determine or whose future usefulness they eliminate.

Work through an example

Temperatures [73,71,74] leave 73 and 71 pending until 74 resolves both. Although one step pops twice, each index leaves only once.

Time and space complexity

O(n) total time/O(n) space, by one push and at most one pop per index.

Why it works

Stack temperatures are nonincreasing; each stored index has no warmer later day seen yet.

Common mistakes

Strict versus non-strict comparisons decide how duplicates behave.
Store indices when answers need distances.

Chapter lab · Python implementation

A stack preserves last-in-first-out order. The lab resolves next-warmer-day queries using a monotonic stack of unresolved indices. Each index is pushed once and popped at most once. This explains why a nested while loop can still do linear total work.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def valid_brackets(text):
    stack=[]
    pairs={')':'(',']':'[','}':'{'}
    for char in text:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop()!=pairs[char]:
                return False
        else:
            raise ValueError('brackets only')
    return not stack

def warmer(temperatures):
    answer=[0]*len(temperatures)
    stack=[]
    for i,temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]]<temp:
            j=stack.pop()
            answer[j]=i-j
        stack.append(i)
    return answer

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert valid_brackets('([])')
assert not valid_brackets('([)]')
assert valid_brackets('')
assert warmer([73,71,74])==[2,1,0]
assert warmer([5,5,5])==[0,0,0]

CHECK YOUR UNDERSTANDING