Next greater/smaller reasoning

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

Next greater/smaller queries pair a position with the first later value satisfying an inequality. Store unresolved indices; resolve when the current value qualifies. Histogram boundaries use related nearest-smaller reasoning.

Work through an example

For [2,1,3], next-greater values are [3,3,None]. For a histogram bar, width extends between the nearest smaller boundaries, excluding those boundaries.

Time and space complexity

O(n) time/O(n) stack; histogram output can be summarized in O(1) extra result state.

Why it works

A popped position's current resolver is the first qualifying later index.

Common mistakes

Equal-height histogram handling needs a consistent rule.
Distance and value answers require different outputs.

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