739. Daily Temperatures — LeetCode(Python)

I got you!

Problem:

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

Solution:

stack = []
ans = [0] * len(temperatures)
for r in range(len(temperatures)):
            
    while stack and temperatures[r] > temperatures[stack[-1]]:
        l = stack.pop()
        ans[l] = r - l
                
    stack.append(r)
            
return ans

Explanation —

We use a stack to solve this problem.

We keep the last warmest day on top of our stack.

As we traverse the list and find a day that is warmer than the top of the stack, we pop from the stack and update the difference in days as our answer ans.

We also shift our left pointer which is now pointing to the last updated answer.

Finally, we return our ans array.

Time and Space Complexity —

Since we are iterating over the array only once, we can say that our algorithm requires a linear amount of time to run.

Also, we need to store some elements in our stack, which in the worst case could be storing all elements from our list of temperatures. So, we can say that we require a linear amount of space for our algorithm to work.

Thus, if n is the length of the list temperatures,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏