Daily Temperatures LeetCode

Key takeaways:
Efficient stack-based approach: The optimal way to solve the Daily Temperatures problem is by using a stack, which reduces time complexity to $O(n)$ .
Improves algorithm skills: This problem enhances proficiency in working with arrays and stacks, making it a strong addition to your coding interview preparation.
Real-world applicability: The problem simulates scenarios where analyzing sequential data efficiently is key, as in weather forecasting or stock price analysis.
Commonly asked in interviews: Daily Temperatures is a frequently asked question in technical interviews at top-tier companies like Amazon, Google, and Microsoft.

What is the Daily Temperature problem?

The Daily Temperatures problem on LeetCode is a popular coding challenge frequently asked in technical interviews by leading tech companies like Google, Amazon, and Microsoft. It tests our ability to work with data structures like stacks and efficiently devise algorithms to solve real-world problems. In this problem, we’re given a list of daily temperatures, and for each day, we must determine how many days it will take for a warmer temperature to occur; if no warmer day is possible, the answer is 0. This problem is an excellent exercise for practicing arrays and stacks, making it a common choice for coding interviews, and helps improve our proficiency in efficiently analyzing and handling data.

Problem statement

Given an integer array temperatures, where each element represents the temperature of a specific day, return an array result such that result[i] indicates the number of days we must wait after the i-th day to experience a warmer temperature. If no warmer temperature is possible for that day, the value in result[i] should be 0.

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:

Daily Temperatures

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

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

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

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

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

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

Question 1 of 50 attempted

Solution

Naive brute force solution

A naive approach to this problem involves using two nested 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 with the time complexity of $O$ (n²) as 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.

Optimal stack-based solution

To make the solution more efficient, we use a stack to store the indexes of days with unresolved temperatures, i.e., days 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, as initially, the stack is empty, and there is no index available for comparison. As we continue, 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. Finally, the current day’s index is added to the stack for future comparisons. This means each day is only checked a few times, making the process much faster. Since each day is added and removed from the stack only once, this solution operates in linear time, $O(n)$ .

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:

main.py

Stack.py

from Stack import Stack
def dailytemperatures(temperatures):
    # Create a stack to store indexes of temperatures
    stack = Stack()
    # Initialize a result list with zeros, same length as temperatures
    result = [0] * len(temperatures)
    # Loop through each temperature in the list
    for 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 stack
        while not stack.is_empty() and temperatures[i] > temperatures[stack.peek()]:
            
            # Get the index present at the top of the stack
            prev_index = stack.pop()
            # Calculate the number of days the previous temperature stayed warmer
            result[prev_index] = i - prev_index
        # Push the current temperature's index onto the stack
        stack.push(i)
    # Return the final result list
    return result
# Driver code
def 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 = dailytemperatures(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, such as daily temperatures, by teaching you to recognize patterns and apply the right algorithms.

Time complexity

Since each element is pushed onto the stack once and popped from the stack at most once, the time complexity of this solution is $O(n)$ , where $n$ is the length of the input list 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.

Space complexity

The space complexity of the solution is $O(n)$ , primarily due to the stack, which can grow to the size of the input in the worst case. While the result list also has a size of $O(n)$ , it is considered part of the output rather than auxiliary space. Therefore, the effective space complexity is driven by the stack usage alone, leading to an overall space complexity of $O(n)$ .

Practice resources for LeetCode problems

To further strengthen your coding skills and boost your technical interview preparation, here are some LeetCode problems to practice:

Also, you can explore these courses designed specifically to help you ace technical interviews:

Moreover, if you’re confident in your preparation, consider trying Educative’s AI-powered mock interviews. Mock interviews are excellent for building confidence, sharpening problem-solving skills, and identifying areas to improve before the actual interview.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

Why is the stack used in the Daily Temperatures problem?

The stack stores indexes of temperatures that have not yet found a warmer day. Using a stack, we can efficiently compare temperatures and avoid needing a nested loop, reducing the time complexity to $O(n)$ .

Can Daily Temperatures be solved without a stack?

Yes, it can be solved with a brute-force approach using two loops, but this method results in a time complexity of $O(n^2)$ , which is inefficient for large inputs.

Which companies test the Daily Temperatures problem in their interviews?

Leading tech companies, including Google, Amazon, and Microsoft, commonly ask this problem as part of their technical interview process.

What skills can I improve by solving Daily Temperatures on LeetCode?

Solving this problem will enhance your understanding of stack-based algorithms, time complexity optimization, and working with arrays in real-world scenarios.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments