DSA Monotonic Stack

A monotonic stack is a regular stack that keeps its items in a strict order, either always increasing or always decreasing from bottom to top. The program removes items that break the order before adding a new one. The trick solves "next greater" and "next smaller" questions in a single pass.

Imagine people standing in a queue for a concert, all facing forward. Each person wants to know who stands taller somewhere behind them. A tall person blocks the view for shorter people in front. Once a tall person arrives, every shorter person in front of them has their answer, and those shorter people leave the waiting list.

The Problem It Solves

A common question asks: for each number in a list, which number to its right is the first one larger than it? A beginner compares every item with all later items, which costs O(n²). A monotonic stack finishes the job in O(n).

The Idea

• Store indexes of items still waiting for a bigger neighbor.
• Read the next number. While the number beats the item at the top of the stack, pop that item and record the answer.
• Push the current index onto the stack.

The stack stays in decreasing order of values from bottom to top, since any smaller item on top gets removed by a bigger arrival.

Example: Next Greater Element

def next_greater(numbers):
    result = [-1] * len(numbers)
    stack = []                      # holds indexes
    for i, n in enumerate(numbers):
        while stack and numbers[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result

print(next_greater([4, 5, 2, 10, 8]))   # [5, 10, 10, -1, -1]

numbers: 4  5  2  10  8

i=0 (4):  stack [0]
i=1 (5):  5 > 4, pop 0, answer for 4 = 5.   stack [1]
i=2 (2):  stack [1, 2]
i=3 (10): 10 > 2, pop 2, answer for 2 = 10
          10 > 5, pop 1, answer for 5 = 10.  stack [3]
i=4 (8):  stack [3, 4]

Items left on the stack have no greater element: -1

Example: Daily Temperatures

Given daily temperatures, find how many days each day must wait for a warmer day.

def days_to_wait(temps):
    result = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(days_to_wait([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Day 3 reads 71 and waits 2 days for 72 on day 5. Day 6 reads 76 and never sees a warmer day, so the answer stays 0.

Why It Runs in O(n)

Each index enters the stack once and leaves the stack at most once. The inner while loop looks scary, yet the total number of pops across the whole run never exceeds n. That count gives the O(n) bound.

Increasing vs Decreasing Stacks

• A decreasing stack finds the next greater item, as in the examples above.
• An increasing stack finds the next smaller item. Flip the comparison from < to >.

Real-Life Uses

Stock apps compute how many days pass before a price rises. Skyline tools find which buildings block the view of others. Text editors match brackets with a similar stack idea. Histogram problems, such as finding the largest rectangle inside a bar chart, rely on the same approach.

Common Mistakes

Storing values instead of indexes loses the position information needed to fill the answer array. Choosing the wrong comparison direction flips next greater into next smaller. Forgetting to set a default for leftover stack items leaves wrong answers. Trace a four-item list on paper before coding to confirm the direction.

Complexity Summary

• Time: O(n)
• Space: O(n) for the stack and result list

Key Points

• A monotonic stack keeps its items in sorted order.
• Arriving items pop smaller items and settle their answers.
• The stack usually stores indexes, not values.
• Each item enters and leaves once, so the run takes O(n) time.
• The method solves next greater and next smaller problems.