How do you approach Daily Temperatures?

Use a stack to keep track of indices of temperatures we haven't found a warmer day for.

What is the time complexity of Daily Temperatures?

Time complexity: O(n) - each element is pushed and popped at most once. Space complexity: O(n) for the stack.

What are common mistakes on Daily Temperatures?

Picking the wrong strictness. > and >= differ only on ties, and ties are where these problems keep their test cases. Not draining the stack after the loop, which drops every element that never found its boundary. Storing values when the answer is a distance, which needs indices.

gitGood.dev

← Back to problems

Daily Temperatures

MediumData Structures

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

Daily Temperatures: approach, complexity and pitfalls

A medium monotonic stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Monotonic Stack

A stack kept sorted, for next-greater and largest-rectangle style questions.

Reach for it when you see: "Next greater/smaller element", or a maximum rectangle/area over a histogram.

More Monotonic Stackproblems →

If you are stuck

Show the 3-step hint ladder

Use a stack to keep track of indices of temperatures we haven't found a warmer day for.
The stack should be monotonically decreasing in temperature values.
When you find a warmer temperature, pop from the stack and calculate the difference in indices.

The optimal approach

Show the approach: Monotonic Stack

Use a stack to store indices of temperatures in decreasing order. For each new temperature, pop all stack entries with lower temperatures and compute the day difference. Push the current index onto the stack.

Time: O(n) - each element is pushed and popped at most once
Space: O(n) for the stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Monotonic Stack mistakes

These apply to the pattern as a whole, not just this problem.

Picking the wrong strictness. `>` and `>=` differ only on ties, and ties are where these problems keep their test cases.
Not draining the stack after the loop, which drops every element that never found its boundary.
Storing values when the answer is a distance, which needs indices.