Day 12: Daily Temperatures- leetcode - Python3

                               

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:

class Solution:

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        result: List[int] = [0]*len(temperatures)

        #so rest of the values will be zero

        stack: List[int] = []

        for i, t in enumerate(temperatures):

            while stack and t > stack[-1][0]:

                stackTemp, stackIndex = stack.pop()# memory

                result[stackIndex] = i-stackIndex

               

            stack.append([t, i])

        return result

Time Complexity: O(n)

Space Complexity: O(n)

The code works as follows:

1. The function creates a list called result to store the results. The list is initialized to all zeros.
2. The function creates a stack to store the temperatures that have been processed so far.
3. The function iterates over the temperatures array.
4. For each temperature, the function checks the stack.
5. If the stack is not empty and the current temperature is greater than the top element of the stack, then the function pops the top element of the stack and stores the difference between the current index and the index of the popped element in the result list.
6. The function then pushes the current temperature and index onto the stack.
7. The function returns the result list.