Daily Temperature Variations — Problem Statement & Solution Guide

StackMediumMonotonic Stack

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Stack and solve the Daily Temperature Variations problem optimally.

TopicStack

PatternMonotonic Stack

TimeO(n)

SpaceO(n)

Problem Description

You are provided with an array temps representing the recorded temperature (in degrees) for each day over a consecutive period. Your task is to determine, for every day in the sequence, how many days one must wait until a strictly higher temperature is recorded. If no subsequent day exhibits a higher temperature, the wait time for that day is defined as 0.

Formally, for each index i in the range [0, n-1], find the smallest index j such that j > i and temps[j] > temps[i]. The value at position i in the result array should be j - i. If no such j exists, the value is 0.

Return an array of the same length as temps containing these computed wait times.

DSA Pattern Breakdown

"Daily Temperature Variations"

medium

WHY DOES IT MATTER?

The Monotonic Stack pattern is essential for solving problems involving 'next greater/smaller element' or 'previous greater/smaller element' in linear time. It is a cornerstone of efficient algorithm design for sequence-based problems, particularly in scenarios where naive O(n^2) solutions are too slow. Mastering this pattern allows engineers to tackle a wide range of interview questions and real-world data processing tasks with optimal performance.

OPTIMIZATION CHALLENGE

The key insight is that once a day's temperature is found to be lower than a subsequent day's temperature, it can never be the answer for any earlier day. Therefore, it can be safely removed from consideration (popped from the stack). This pruning of irrelevant elements reduces the number of comparisons from O(n^2) to O(n), as each element is processed at most twice (once pushed, once popped).

REAL-WORLD CONNECTION

This pattern is analogous to managing a queue of pending tasks in a distributed system where each task has a deadline. The stack represents tasks that are still waiting for a condition to be met (e.g., a higher priority task arriving). When a new task arrives that satisfies the condition for the top of the stack, the pending task is resolved and removed. This ensures that no task is checked repeatedly, optimizing resource usage and latency.

During an interview, explicitly state that you are using a Monotonic Stack and explain why it is O(n) (amortized). Emphasize that the stack stores indices, not values, to allow easy calculation of the wait time (current index - popped index). Also, mention that the stack is monotonic decreasing in terms of temperature values, which is the invariant that ensures correctness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem of determining the number of days until a strictly higher temperature is a classic application of the Monotonic Stack pattern. A naive approach involves iterating through the array for each day and scanning forward until a higher temperature is found, resulting in O(n^2) time complexity. This becomes infeasible for large datasets (e.g., n = 10^5 or 10^6), where the quadratic growth leads to timeouts in competitive programming and production environments. The core theoretical insight is that we do not need to check every future day for every current day; instead, we can maintain a stack of indices representing days for which we have not yet found a higher temperature. This stack remains monotonic (specifically, decreasing in terms of temperature values) because if a new day's temperature is higher than the top of the stack, it resolves the wait time for that top element, and we pop it. This ensures that each element is pushed and popped at most once, leading to an amortized O(n) time complexity.

Interview Questions on This Problem

Q1At a fintech platform processing real-time stock price data, how would you adapt the Daily Temperature Variations logic to find the next day where the price drops below the current price?

You would invert the comparison logic. Instead of popping when the current price is strictly greater than the stack top, you pop when the current price is strictly less than the stack top. The stack would maintain a monotonic increasing sequence of prices. The answer for each popped index would still be the difference between the current index and the popped index. This demonstrates the flexibility of the Monotonic Stack pattern for both 'next greater' and 'next smaller' element problems.

Q2In a distributed systems context, if the temperature array is split across multiple nodes, how does the Monotonic Stack approach handle the boundary conditions between nodes?

The Monotonic Stack is inherently sequential and stateful, making it difficult to parallelize directly without significant overhead. However, for boundary conditions, you must ensure that the stack from the previous node is passed to the next node, or that the algorithm is re-run on the combined boundary segments. In practice, for large-scale distributed data, one might use a divide-and-conquer approach where each node computes local next greater elements, and then a merge step resolves cross-node dependencies. The key is that the stack state (indices and values) must be preserved across partitions to maintain correctness.

Q3At a high-growth startup, if the input array is circular (i.e., day 0 follows the last day), how would you modify the algorithm to handle wrap-around?

You can simulate a circular array by iterating through the array twice (2n iterations). Use a modulo operation (i % n) to access the temperature values. The stack will still maintain monotonicity, but you must be careful to only record the answer for indices in the first pass (i < n) to avoid overwriting results. This ensures that elements near the end of the array can find their next greater element in the beginning of the array, effectively handling the circular dependency.

Examples

Example 1

Input

temps = [72, 75, 71, 78, 74, 80, 76]

Output

[1,2,1,2,1,0,0]

Explanation: Day 0 (72): Next warmer is Day 1 (75). Wait = 1 - 0 = 1. Day 1 (75): Next warmer is Day 3 (78). Wait = 3 - 1 = 2? No, check Day 2 (71) is lower. Day 3 is 78 > 75. Wait = 3 - 1 = 2. Wait, let me re-verify. 75 -> 71 (no) -> 78 (yes). Index 3. 3-1=2. My previous output said 3. Let me re-calculate carefully. Day 0: 72. Next is 75 (idx 1). 1-0=1. Day 1: 75. Next is 71 (no), 78 (yes, idx 3). 3-1=2. Day 2: 71. Next is 78 (yes, idx 3). 3-2=1. Day 3: 78. Next is 74 (no), 80 (yes, idx 5). 5-3=2. Day 4: 74. Next is 80 (yes, idx 5). 5-4=1. Day 5: 80. Next is 76 (no). End. 0. Day 6: 76. End. 0. Correct Output: [1, 2, 1, 2, 1, 0, 0]. Let me adjust the example to be distinct and correct. Input: [72, 75, 71, 78, 74, 80, 76] Output: [1, 2, 1, 2, 1, 0, 0]

Example 2

Input

temps = [50, 50, 50, 51, 50]

Output

[3, 2, 1, 0, 0]

Explanation: Day 0 (50): Next strictly higher is Day 3 (51). Wait = 3 - 0 = 3. Day 1 (50): Next strictly higher is Day 3 (51). Wait = 3 - 1 = 2. Day 2 (50): Next strictly higher is Day 3 (51). Wait = 3 - 2 = 1. Day 3 (51): Next is 50 (not higher). No warmer day. Wait = 0. Day 4 (50): No subsequent days. Wait = 0.

Example 3

Input

temps = [90, 85, 80, 75, 70]

Output

[0, 0, 0, 0, 0]

Explanation: The temperatures are strictly decreasing. For every day, all subsequent days have lower temperatures. Therefore, no warmer day exists for any index. All values are 0.

Example 4

Input

temps = [10, 20, 30, 40, 50]

Output

[1, 1, 1, 1, 0]

Explanation: The temperatures are strictly increasing. For each day `i` (where `i < n-1`), the very next day `i+1` has a higher temperature. Wait = (i+1) - i = 1. The last day has no subsequent days, so wait is 0.

Constraints

1 <= temps.length <= 10^5
1 <= temps[i] <= 10^9
The input array contains integers only.

Optimal Approach & Strategy

Use a Monotonic Stack to store indices of days for which a higher temperature has not yet been found. For each new day, pop indices from the stack while the current temperature is strictly higher than the temperature at the top of the stack, recording the wait time for each popped index. Push the current index onto the stack if it has not been resolved. This achieves O(n) time complexity.

Brute Force Approach

For each day, iterate through all subsequent days until a strictly higher temperature is found, counting the number of days waited. If no higher temperature is found, the wait time is 0. This results in O(n^2) time complexity, which is inefficient for large inputs.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function dailyTemperatures(temps) {
    const n = temps.length;
    const res = new Array(n).fill(0);
    const stack = []; // indices
    for (let i = 0; i < n; i++) {
        while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
            const idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
}

#include <vector>
#include <stack>
using namespace std;

vector<int> dailyTemperatures(vector<int>& temps) {
    int n = temps.size();
    vector<int> res(n, 0);
    stack<int> st; // indices of days with unresolved temperatures
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && temps[i] > temps[st.top()]) {
            int idx = st.top(); st.pop();
            res[idx] = i - idx;
        }
        st.push(i);
    }
    return res;
}

import java.util.*;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // indices
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}

def dailyTemperatures(temps):
    n = len(temps)
    res = [0] * n
    stack = []  # indices
    for i, t in enumerate(temps):
        while stack and t > temps[stack[-1]]:
            idx = stack.pop()
            res[idx] = i - idx
        stack.append(i)
    return res

function dailyTemperatures(temps) {
    const n = temps.length;
    const res = new Array(n).fill(0);
    const stack = []; // indices
    for (let i = 0; i < n; i++) {
        while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
            const idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
}

Asked in Top Tech Interviews

Infosys

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.