Daily Temperatures

LeetCode 739 | Difficulty: Medium

Medium

Problem Description

Given an array of integers temperatures represents the daily 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 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5

• 30 <= temperatures[i] <= 100

Topics: Array, Stack, Monotonic Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 344 ms)

Metric	Value
Runtime	344 ms
Memory	41 MB
Date	2019-12-28

Solution

public class Solution {
    public int[] DailyTemperatures(int[] T) {
        Stack<int> stack = new Stack<int>();
	int[] ans = new int[T.Length];

	for (int i = T.Length - 1; i >= 0; i--)
	{
		while (stack.Count!=0 && T[i] >= T[stack.Peek()])
		{
			stack.Pop();
		}

		ans[i] = stack.Count == 0 ? 0 : stack.Peek() - i;
		stack.Push(i);
	}

	return ans;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, ..., 99, or 100. We could remember when all of them occur next.