Home/Questions/Q 3540
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:54:00-05:00 In: ,

Daily Temperatures: How to use an Index-Tracking Monotonic Stack for next warmer day in O(N)

Given an array of integers temperatures, we need to 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.

Brute force nested loops take O(N^2) time. How does storing array indices instead of temperature values in a decreasing monotonic stack solve this in a single pass?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    This problem is the cleanest introductory template for the Monotonic Decreasing Stack pattern. Let’s look at why storing indices unlocks the distance calculation.

    1. The Mental Model

    Imagine people waiting in line holding temperature tickets. If temperatures are dropping: [73, 71, 69], nobody has found a warmer day yet! So everyone has to stay waiting in line.

    Now, a warm day arrives: 72!

    • The person holding 69 sees 72 > 69. Their wait is over! They step out of line.
    • The person holding 71 sees 72 > 71. Their wait is over! They step out of line.
    • The person holding 73 sees 72 < 73. 72 is not warm enough for them! The person with 73 stays waiting in line, and the day with 72 joins the line behind them.

    2. Why Store Indices Instead of Values?

    If you only push temperature numbers (e.g. 69) onto the stack, when a warmer day 72 pops 69, you know that a warmer day happened, but you don’t know how many days elapsed!

    By pushing the array index prev_day onto the stack:

    days_waited = current_day - prev_day
answer[prev_day] = days_waited

    You calculate the exact time difference in $O(1)$ and write directly to the output array!

    Clean Python 3.12 Implementation

    def daily_temperatures(temperatures: list[int]) -> list[int]:
    """Finds wait time until warmer day in O(N) time and O(N) auxiliary space."""
    n = len(temperatures)
    ans = [0] * n
    stack: list[int] = [] # Stores indices of previous cooler days

    for curr_day, temp in enumerate(temperatures):
        # Pop all previous days that are strictly cooler than today
        while stack and temperatures[stack[-1]] < temp:
            prev_day = stack.pop()
            ans[prev_day] = curr_day - prev_day

        stack.append(curr_day)

    return ans

    Complexity Breakdown

    • Time Complexity: O(N). Every index is pushed onto the stack once and popped at most once. Total operations: $le 2N$.
    • Space Complexity: O(N) for the stack in the worst-case of strictly decreasing temperatures (e.g. [100, 90, 80, 70]).
    • 0
  2. Abhishek
    Begginer

    Here is the C++20 Monotonic Stack solution for Daily Temperatures. It stores day indices to compute elapsed days in O(1).

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>

std::vector<int> dailyTemperatures(const std::vector<int>& temperatures) {
    const size_t n = temperatures.size();
    std::vector<int> ans(n, 0);
    std::vector<int> stack;
    stack.reserve(n);

    for (int curr_day = 0; curr_day < static_cast<int>(n); ++curr_day) {
        while (!stack.empty() && temperatures[stack.back()] < temperatures[curr_day]) {
            int prev_day = stack.back();
            stack.pop_back();
            ans[prev_day] = curr_day - prev_day;
        }
        stack.push_back(curr_day);
    }
    return ans;
}

int main() {
    std::vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    auto res = dailyTemperatures(temps);
    std::cout << "Days to wait for warmer temperature: ";
    for (int d : res) std::cout << d << " ";
    std::cout << "n";
    return 0;
}

    Complexity: O(N) time and O(N) space with zero reallocations.

    • 0