Teaching to learn: Daily Temperatures

Shane Quick
May 7, 2020 · 4 min read
Leetcode: Daily Temperatures

This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.

Daily Temperatures is categorized as a medium difficulty. I would agree with this. I was able to solve for the naive solution relatively easily but a more efficient solution was not as obvious. Let’s take a look at which solutions I was able to understand.

This challenge can be found here.

Understanding the problem

We are given an array of sequential daily Temperatures, T, that have a temperature range between 30 and 100.

For each daily temperature in T we are asked to find the number of days until the next warmer day (looking forward into the future only).

We will be returning an array of days in between the current temperature and the next warmer day.

For example:

if we have an array T = [30, 31, 46, 68, 55, 74]

then our output would be days = [1,1,1,2,1,0]

If you looks at index 3 in T (T[3]= 68) you’ll notice the next day is not warmer (T[4] = 55). But they day after that is (T[5] = 74). If we subtract the indices of these two, the higher temp from the lower temp, then we get 5–3=2. Two is our answer so we have to place it in the days array at the correct index corresponding to the lower temp day (3). So we could say days[3] = 2. Check the output above and you will see this is correct.

One thing I noticed right off the bat is that the last item in our return array will always be 0 since there are no warmer temperatures that follow it. This may or may not be useful, but it’s nice to be aware of.

Let’s look at what the naive approach’s steps are.

Pseudo-code:

  1. Initialize an empty array to store # of days until a warmer temp: let days
  2. Loop over input T, for each temperature, compare to index + 1 in input T
  3. Search for first value larger than the current temperature
  4. Store the difference of their indices in the days array
  5. When finished looping, return the days array

The code:

O(n²) Time Complexity / O(n) Space Complexity

I was able to submit this solution and have it accepted but the runtime was around 700ms. The time complexity is O(n²) since we are using a nested for loop to check each temperature against every other temperature in the same array that comes after the current temperature. That is pretty bad. I think we can do better!

Another Solution:

This problem lends itself to utilizing a stack since we are passing over data that can be processed later on as we encounter different temperatures.

As we go through the array T we can add the index of each temperature to a stack and check that stack on each iteration. We can check if the current temperature we are looking at is greater than the temps in the stack which are looking for a future-warmer-day.

If our current temp is higher than a temp in the stack, then we pop it off the stack and add the difference of our current index minus the popped value (the index of a previous temp).

Pseudo-code:

  1. Initialize an empty array for # of days that is the length of input T, filled with 0's
  2. Initialize an empty stack array which will hold indices of each temp in T
  3. Loop over input T length
  4. While stack is not empty and current temp is greater than top element in the stack (T[stacklength-1]) repeat step 5.
  5. Pop from the stack, set days[index-popped] = i -index-popped
  6. Outside while loop, push current index to the stack
  7. Once for loop completes, return days array

The code:

O(n) Time Complexity / O(n) Space complexity

The most important part of this function is the while loop conditions. We only want to pop from the stack when there are values in the stack and when the current temperature is greater than the value on top of our stack.

This insures that all of our temps-with-warmer-future-days will be changed from a 0 to the correct number of days between the next warmer day in our days array.

This algorithm has a much better time complexity at O(n) with the same space complexity as the previous solution: O(n).

If you have another solution for this challenge or any pointers for me, let me know. Thanks!

The Startup

Get smarter at building your thing. Join The Startup’s +792K followers.

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Shane Quick

Written by

Full Stack Developer writing about my interests and thoughts.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +792K followers.

Shane Quick

Written by

Full Stack Developer writing about my interests and thoughts.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +792K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store