algorithms.live
    DSA
    intermediate

    Monotonic Stack

    Monotonic Stack: Next Greater Element

    Find the first larger element to the right for every element in the array.

    ⏱ O(n)
    💾 O(n)
    Ready
    Input Array
    2
    0
    1
    1
    2
    2
    4
    3
    3
    4
    Result Array (NGE)
    -
    0
    -
    1
    -
    2
    -
    3
    -
    4
    Stack (Indices)

    Initialize empty stack and result array with -1.

    Initialize empty stack and result array with -1.

    50%
    Live Variables
    i-1
    stack

    Next greater element

    Sequence

    Order what the algorithm does for each element, scanning left to right.

    Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.

    1. 1Drop a step here
    2. 2Drop a step here
    3. 3Drop a step here
    4. 4Drop a step here
    5. 5Drop a step here
    5 pieces left to place

    Test your knowledge

    20 questions
    Question 1 of 20
    Score: 0

    When should you use a Monotonic Stack?

    Write the code

    Runs your solution

    Daily Temperatures

    Return an array `answer` such that `answer[i]` is the number of days you have to wait after the ith day to get a warmer temperature.

    Example Cases

    Input:[[73,74,75,71,69,72,76,73]]
    Output:[1,1,4,2,1,1,0,0]
    Input:[[30,40,50,60]]
    Output:[1,1,1,0]
    Input:[[30,60,90]]
    Output:[1,1,0]
    javascript

    The short version

    Think of looking for a view in a city skyline. If a taller building is in front of you, it blocks your view of smaller buildings behind it. You only see the 'next greater' building.

    In more depth

    Maintaining Order

    A Monotonic Stack is a stack that always stays sorted (increasing or decreasing) from bottom to top. Before pushing a new element, you pop any elements that would violate the chosen order — and those pops are the payoff: each popped element just found its nearest greater or smaller neighbour.

    Monotonic Decreasing Stack: pop elements smaller than the incoming value → the incoming element is the Next Greater Element for every popped item.
    Monotonic Increasing Stack: pop elements larger than the incoming value → the incoming element is the Next Smaller Element for every popped item.

    Why O(n) — Amortised Analysis

    Each element is pushed exactly once and popped at most once. Total push + pop operations across the entire scan ≤ 2n, so the inner while-loop does not change the overall complexity: it is O(n) amortised. This is the argument interviewers expect you to articulate.

    Worked Example (NGE, decreasing stack)

    Input: [2, 1, 2, 4, 3]

    i=0 (2): push 0. Stack indices=[0]
    i=1 (1): 1 < 2, push 1. Stack=[0,1]
    i=2 (2): 2 > arr[1]=1 → pop 1, result[1]=2. 2 = arr[0]=2, not >, push 2. Stack=[0,2]
    i=3 (4): 4 > arr[2]=2 → pop 2, result[2]=4. 4 > arr[0]=2 → pop 0, result[0]=4. Push 3. Stack=[3]
    i=4 (3): 3 < 4, push 4. Stack=[3,4]
    End: indices 3 and 4 have no NGE → result stays -1

    Final result: [4, 2, 4, -1, -1]

    Choosing the Variant

    GoalStack orderPop condition
    Next Greater ElementDecreasingincoming > top value
    Next Smaller ElementIncreasingincoming < top value
    Stock SpanDecreasingincoming >= top value
    Previous Greater ElementDecreasing (right-to-left scan)incoming > top value

    Classic Problem Mapping

    Daily Temperatures (LeetCode 739): decreasing stack of day indices; span = current index − popped index.
    Largest Rectangle in Histogram (LeetCode 84): increasing stack of indices; area = height × (right_bound − left_bound − 1) on pop.
    Trapping Rain Water (LeetCode 42): decreasing stack; trapped water = min(current, new top) × (current_i − new_top_i − 1) per pop.
    Stock Span (LeetCode 901): decreasing stack of (index, price) pairs.

    When to reach for this

    • Find the **Next Greater Element** or **Next Smaller Element**
    • Find width of a rectangle in histogram
    • Stock span problems

    Interview Questions

    Amazon
    Google
    Microsoft
    Amazon
    Microsoft
    Bloomberg
    Facebook
    Uber
    Airbnb
    Citadel
    Uber
    Palantir

    References & Further Reading

    Monotonic Stack in 6 minutes | LeetCode PatternYouTube
    video
    Introduction to Monotonic StackGeeksforGeeks
    article
    Monotonic Stack code templatelabuladong
    article

    Love this visualization?

    Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.

    100% free • No credit card required