Daily Temperatures

Daily Temperatures is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.

Problem statement

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 ith 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 <= 105

- 30 <= temperatures[i] <= 100

Topics and companies

Topics: Array, Stack, Monotonic Stack.

Reported in interviews at Facebook, Bloomberg, Amazon, ByteDance, Google, Adobe, Microsoft, Paypal, Oracle, Salesforce, Twitter.

How to practise Daily Temperatures on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of days (temperatures.size()). Each index is pushed and popped from the stack at most once. time and O(N), for the answer vector and the stack which in the worst case can hold all indices. space.

Open Daily Temperatures in the code editor, or read the Daily Temperatures editorial for a worked solution with its approach and complexity analysis.

Where Daily Temperatures sits in the DSA pattern sheet

Problems related to Daily Temperatures

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

Opening the problem

Progress is saved as you study.