Monotonic Stack

    DSA · Intermediate

    Definition

    A monotonic stack keeps elements in increasing or decreasing order to find next greater/smaller elements.

    Solves next greater element, stock span and largest rectangle in O(n).

    Diagram

    stack: 5 3see 4 → pop 3stack: 5 4

    Flowchart

    Loop over elementsPop while top is smallerPopped elements get current as answerPush current

    Example: Next greater element

    a = [2, 1, 3]
res = [-1] * len(a)
st = []
for i, x in enumerate(a):
    while st and a[st[-1]] < x:
        res[st.pop()] = x
    st.append(i)
print(res)

    Output: [3, 3, -1]

    Complexity

    O(n) — each element pushed and popped once

    Key points

    • Store indexes, not values
    • Decreasing stack finds next greater

    Interview questions

    Why O(n) despite a nested loop?

    Each index is pushed and popped at most once.

    More DSA topics

    ArraysLinked ListStackQueue