Daily Temperatures 2 — Problem Statement & Solution Guide

StackMediumMonotonic Stack

TimeO(n)

SpaceO(n)

Problem Description

You are monitoring a sequence of $n$ daily thermal efficiency readings from a solar array, represented by an integer array temps where temps[i] denotes the efficiency metric on day $i$. For each day $i$, determine the number of days you must wait until a day with a strictly higher efficiency metric occurs. If no such future day exists, the wait time is 0.

Specifically, 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 answer for day $i$ is $j - i$. If no such $j$ exists, the answer is 0.

Return an array ans of length $n$ where ans[i] is the computed wait time for day $i$.

DSA Pattern Breakdown

"Daily Temperatures 2"

medium

WHY DOES IT MATTER?

The monotonic stack pattern solves a family of problems where you need the next greater (or smaller) element in a linear sequence. Mastering this pattern equips engineers to handle real‑time analytics, stock span calculations, and load‑balancing decisions where immediate future thresholds matter.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that each index only needs to be examined once. By maintaining a decreasing stack, you turn a potentially O(n²) scan into a series of push/pop operations, each O(1) amortized, thus collapsing the total work to O(n).

REAL-WORLD CONNECTION

Think of a distributed load balancer that routes requests to servers with higher capacity. As traffic spikes, the balancer must quickly find the next server that can handle the load without scanning the entire pool each time—mirroring how the stack jumps directly to the next suitable temperature.

During an interview, write the stack loop first, then immediately add a comment explaining why the stack is monotonic. This shows you understand the invariant, and it also helps you avoid off‑by‑one errors when computing the distance.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The Daily Temperatures problem is a classic example of a "next greater element" query on an array. The naive solution scans forward from each index, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n > 10⁵) because the number of comparisons grows quadratically. The optimal paradigm leverages a monotonic decreasing stack: we traverse the temperature list once, maintaining indices of days whose next warmer day hasn't been found yet. When we encounter a temperature higher than the temperature at the stack's top, we pop that index, compute the distance, and continue until the stack is empty or the current temperature is not greater. This ensures each index is pushed and popped at most once, guaranteeing linear time.

Why does the monotonic stack work? By storing indices in decreasing order of temperature, we guarantee that any future temperature that is higher will be the first warmer day for all lower temperatures stored beneath it. This eliminates redundant comparisons because once a day finds its next warmer day, it never needs to be examined again. The space usage is O(n) in the worst case (strictly decreasing temperatures) but often much lower in practice. This pattern extends to many "next greater" or "nearest larger" problems across arrays, strings, and even binary trees.

Interview Questions on This Problem

Q1How would you modify the solution if you needed to find the number of days until a temperature that is at least twice as high as the current day?

Keep the same monotonic stack but change the comparison to temps[current] >= 2 * temps[stackTop]. When a temperature satisfies the doubled condition, pop indices and record the distance. The stack still remains monotonic because any temperature that fails the condition cannot become a candidate for future days.

Q2Can you solve the problem in O(n) time without using extra space beyond O(1) auxiliary variables?

Yes, by iterating from right to left and using the result array itself as a jump pointer. For each day i, we look at j = i+1; while j < n and temps[j] <= temps[i], we jump j += result[j] (skip days that are not warmer). If j < n, result[i] = j - i; otherwise result[i] = 0. This uses the output array for memoization, achieving O(n) time and O(1) extra space.

Q3Why is a simple priority queue not ideal for this problem compared to a monotonic stack?

A priority queue would give you the maximum temperature seen so far, but it cannot guarantee the *nearest* future warmer day because it loses positional ordering. The monotonic stack preserves both order and value relationships, allowing O(1) amortized updates, whereas a heap would require O(log n) per insertion/removal and still wouldn't directly provide the correct distance.

Examples

Example 1

Input

temps = [4, 5, 2, 10, 3, 8, 7, 9]

Output

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

Explanation: Day 0 (4): Next higher is 5 at day 1. Wait = 1. Day 1 (5): Next higher is 10 at day 3. Wait = 2? No, 10 is at index 3. 3-1=2. Wait, let's re-verify. 5 < 10. Yes. Wait = 2. Let's check the example output provided in thought process. I need to generate a valid example. Let's use: [73, 74, 75, 71, 69, 72, 76, 73] Day 0 (73): Next higher 74 at idx 1. Wait 1. Day 1 (74): Next higher 75 at idx 2. Wait 1. Day 2 (75): Next higher 76 at idx 6. Wait 4. Day 3 (71): Next higher 72 at idx 5. Wait 2. Day 4 (69): Next higher 72 at idx 5. Wait 1. Day 5 (72): Next higher 76 at idx 6. Wait 1. Day 6 (76): No higher. Wait 0. Day 7 (73): No higher. Wait 0. Output: [1, 1, 4, 2, 1, 1, 0, 0] Let's create a new unique example. Input: [10, 20, 15, 30, 25, 40] Day 0 (10): Next higher 20 at idx 1. Wait 1. Day 1 (20): Next higher 30 at idx 3. Wait 2. Day 2 (15): Next higher 30 at idx 3. Wait 1. Day 3 (30): Next higher 40 at idx 5. Wait 2. Day 4 (25): Next higher 40 at idx 5. Wait 1. Day 5 (40): No higher. Wait 0. Output: [1, 2, 1, 2, 1, 0]

Example 2

Input

temps = [5, 5, 5, 5, 5]

Output

[0, 0, 0, 0, 0]

Explanation: All values are equal. Since we require a strictly higher value (`temps[j] > temps[i]`), no future day satisfies the condition for any day. Thus, all wait times are 0.

Example 3

Input

temps = [1, 2, 3, 4, 5]

Output

[1, 1, 1, 1, 0]

Explanation: The array is strictly increasing. Day 0 (1): Next higher is 2 at day 1. Wait = 1. Day 1 (2): Next higher is 3 at day 2. Wait = 1. Day 2 (3): Next higher is 4 at day 3. Wait = 1. Day 3 (4): Next higher is 5 at day 4. Wait = 1. Day 4 (5): No future days. Wait = 0.

Example 4

Input

temps = [5, 4, 3, 2, 1]

Output

[0, 0, 0, 0, 0]

Explanation: The array is strictly decreasing. No future day has a higher value than the current day. Thus, all wait times are 0.

Constraints

1 <= temps.length <= 10^5
1 <= temps[i] <= 10^6

Optimal Approach & Strategy

Traverse the array once while maintaining a decreasing stack of indices. When the current temperature exceeds the temperature at the stack's top, pop and compute the distance. Push the current index onto the stack. This yields O(n) time and O(n) auxiliary space.

Brute Force Approach

For each day i, scan forward until you find a day j > i with temps[j] > temps[i]; record j-i or 0 if none exists. This double loop is O(n²).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} temps
 * @return {number[]}
 */
var dailyTemperatures = function(temps) {
    const n = temps.length;
    const result = new Array(n).fill(0);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    
    return result;
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temps) {
        int n = temps.size();
        vector<int> result(n, 0);
        stack<int> st;
        
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temps[i] > temps[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                result[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        
        return result;
    }
};

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

class Solution:
    def dailyTemperatures(self, temps: List[int]) -> List[int]:
        n = len(temps)
        result = [0] * n
        stack = []
        
        for i in range(n):
            while stack and temps[i] > temps[stack[-1]]:
                prev_index = stack.pop()
                result[prev_index] = i - prev_index
            stack.append(i)
        
        return result

/**
 * @param {number[]} temps
 * @return {number[]}
 */
var dailyTemperatures = function(temps) {
    const n = temps.length;
    const result = new Array(n).fill(0);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    
    return result;
};

Asked in Top Tech Interviews

Flipkart

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.

Daily Temperatures 2 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Daily Temperatures 2 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor