Daily Temperatures — Monotonic Stack Visualization

The Problem

Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0.

Example: For temperatures = [73,74,75,71,69,72,76,73], the answer is [1,1,4,2,1,1,0,0].

Interactive Visualization

Temperatures (comma-separated)

Preset

Speed:

Temperature Bars

Answer Array

Monotonic Stack (indices)

Empty

bottom of stack

Status & Log

Press Step or Play to begin.

Code

fun dailyTemperatures(temperatures: IntArray): IntArray {    val n = temperatures.size    val answer = IntArray(n)  // initialized to 0    val stack = ArrayDeque<Int>()  // indices    for (i in temperatures.indices) {        while (stack.isNotEmpty() && temperatures[stack.last()] < temperatures[i]) {            val j = stack.removeLast()            answer[j] = i - j }        stack.addLast(i) }    return answer}

def dailyTemperatures(temperatures):    n = len(temperatures)    answer = [0] * n    stack = []  # indices    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

How It Works

Key Insight

A monotonic decreasing stack keeps track of indices whose temperatures have not yet found a warmer future day. The stack always holds indices in order such that their corresponding temperatures are non-increasing from bottom to top. When a new temperature is warmer than the top of the stack, we have found the answer for that stack entry.

Algorithm Steps

Initialize: Create an answer array of zeros and an empty stack.
For each day i: Compare the current temperature with the temperature at the index on top of the stack.
While the stack is not empty and the top temperature is less than the current temperature: Pop index j from the stack and set answer[j] = i - j (the number of days waited).
Push the current index i onto the stack — it is now waiting for its own warmer day.
After the loop: Any indices remaining on the stack never found a warmer day, so their answers stay 0.

Why Monotonic?

The stack maintains a decreasing order of temperatures. Each time we push a new index, we first pop all indices with temperatures strictly less than the current one. This guarantees that the stack top always holds the most recently seen temperature that is still ≥ the current temperature.

Complexity

Time O(n)

Space O(n)

Each index is pushed onto the stack exactly once and popped at most once, giving O(n) total stack operations. The stack and answer array each use O(n) space.