algorithms.live
    DSA
    intermediate

    Monotonic Stack

    Software Engineer path · lesson 43 of 99
    time O(n)
    space O(n)

    Up to 12 whole numbers from -99 to 99.

    Try:
    a20112243341556
    next >·0·1·2·3·4·5·6
    stack →0
    CurrentWaiting on stackPopped nowAnswered

    Scan left to right. The stack holds indices still waiting for a bigger value to their right.

    Code (running line highlighted)
    1. 1result = [-1] * n; stack = [] # indices, values decreasing
    2. 2for i in 0 .. n-1:
    3. 3 while stack and a[stack.top] < a[i]:
    4. 4 result[stack.pop()] = a[i]
    5. 5 stack.push(i)
    6. 6return result
    Pushes
    0 / 7
    Pops
    0 / 6
    Invariant: Stack values are strictly decreasing from bottom to top; each is still waiting for a greater value.

    Tap any element in the diagram to inspect its state at this step.

    1 / 22

    Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.

    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
    function dailyTemperatures(temperatures) {
  // Your code here
}

    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
    All Data Structures & Algorithms topics

    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