The **Daily Temperatures** problem on LeetCode is a popular coding challenge that many leading tech companies, like Google, Amazon, and Microsoft, frequently ask in their technical interviews. Its popularity stems from its ability to test a candidate’s proficiency in utilizing data structures, such as stacks, and its capability to devise efficient algorithms for real-world scenarios. In this LeetCode problem, we are given a list of daily temperatures, and we need to find out how many days it will take for each day to get warmer. This exercise is great for practicing how to work with arrays and stacks, making it a common choice for coding interviews and practice. Solving this problem helps programmers improve their skills in efficiently handling and analyzing data.

We have an integer array, `temperatures`

, where each element represents the temperature of a particular day. For each day, we want to find out how many days we would have to wait until a warmer temperature occurs. If there is no future day for which this is possible, keep

**Constraints:**

$1 \leq$ `temperatures.length`

$\leq 10^5$ $30 \leq$ `temperatures[i]`

$\leq 100$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Let’s take a moment to ensure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem.

Daily Temperatures

1

What is the output, if the following temperatures are given as input?

$[68,~ 70,~ 72,~ 71,~ 74,~ 73,~ 75]$

A)

$[1,~ 1,~ 2,~ 1,~ 3,~ 1,~ 0]$

B)

$[1,~ 1,~ 2,~ 1,~ 1,~ 2,~ 0]$

C)

$[1,~ 1,~ 2,~ 1,~ 2,~ 1,~ 0]$

D)

$[2,~ 2,~ 3,~ 2,~ 3,~ 2,~ 0]$

Question 1 of 50 attempted

The first solution that comes to our mind is to use two loops. Against each temperature in `temperatures`

, we check all the subsequent temperatures to see when a warmer temperature comes. This method is simple but very slow because it has to compare many temperatures multiple times, making it inefficient for longer inputs. To overcome this challenge, we use stacks to get to the output in a single go.

We use a stack to keep track of the indexes of days with temperatures that are still waiting for a warmer day. We start with an empty stack and a result list filled with zeros. For the first temperature, we push its index onto the stack and proceed to the next index. This is because, initially, the stack is empty and there is no index available for the comparison. Then, as we proceed, we check if the current temperature is warmer than the temperature at the index on top of the stack. If it is, we calculate how many days it took to get warmer by subtracting the index of the day at the top of the stack from the current day's index. This difference is then placed in the result list at the position of the popped index. We remove the index from the stack and continue this process until the current temperature is not warmer than the temperature at the top of the stack. The current day's index is then added to the stack to be checked later. This means each day is only checked a few times, making the process much faster. Additionally, because each day is added and removed from the stack only once, this solution takes linear time,

Here's how the algorithm works:

Create a

`Stack`

instance to track indexes of temperatures that need a warmer day.Initialize a

`result`

list with zeros, having the same length as the input list`temperatures`

. This list will eventually contain the number of days to wait for a warmer temperature for each day.Iterate over each index

`i`

in the`temperatures`

list, and process it as follows:If the stack is empty:

Push the current index

`i`

onto the stack.

If the stack is not empty:

While the stack is not empty and the current temperature

`temperatures[i]`

is greater than the temperature at the index stored at the top of the stack:Pop the index from the top of the stack and store it in

`prev_index`

.Calculate the number of days until a warmer temperature by subtracting

`prev_index`

from`i`

.Update

`result[prev_index]`

with this difference.

Push the current index

`i`

onto the stack.

Continue this process for all temperatures.

Return the

`result`

list, which now contains the number of days until a warmer temperature for each day.

Note:For the last temperature in the list, there is no future day to check for a warmer temperature, so the wait for the last temperature is always$0$ .

Now, let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for this solution below:

main.py

Stack.py

from Stack import Stackdef daily_temperatures(temperatures):# Create a stack to store indexes of temperaturesstack = Stack()# Initialize a result list with zeros, same length as temperaturesresult = [0] * len(temperatures)# Loop through each temperature in the listfor i in range(len(temperatures)):# While the stack is not empty and the current temperature is higher# than the temperature at the top of the stackwhile not stack.is_empty() and temperatures[i] > temperatures[stack.peek()]:# Get the index present at the top of the stackprev_index = stack.pop()# Calculate the number of days the previous temperature stayed warmerresult[prev_index] = i - prev_index# Push the current temperature's index onto the stackstack.push(i)# Return the final result listreturn result# Driver codedef main():inputs = [[73, 74, 75, 71, 69, 72, 76, 73],[30, 40, 50, 60],[30, 60, 90],[60, 60, 60],[75, 74, 73, 72, 71],[30, 32, 31, 35, 33, 34, 36]]for i, input_temperatures in enumerate(inputs, start=1):print(f"{i}. Temperatures: {input_temperatures}")result = daily_temperatures(input_temperatures)print(f" Days to wait for a warmer temperature: {result}")print("-" * 100, "\n")if __name__ == "__main__":main()

Daily Temperatures

Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity to understand how efficiently it scales with larger inputs.

__Educative 99__ helps you solve complex coding problems like daily temperatures by teaching you to recognize patterns and apply the right algorithms.

Since each element is pushed onto the stack once and popped from the stack at most once, the time complexity of this solution is `temperatures`

. The second loop inside the first loop only runs while the stack is not empty and the current temperature is greater than the temperature at the index at the top of the stack. As each element is processed only a few times, the overall time complexity remains linear.

The space complexity of the solution is `result`

list, which stores the output, also takes up

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS