Skip to content

739. Daily Temperatures

Medium

Description

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 <= 10โต
  • 30 <= temperatures[i] <= 100

Solutions ๐Ÿ”’

Video Solution Coming Soon

Algorithm Discussion

General Procedure of monotonic stack:

To find the nearest number to the left/right of each number that is larger/smaller than it.

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

Approach:Monotonic Stack (Decreasing)

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Monotonic Stack Decreasing template

Template - mono_stack decreasing

def mono_stack(insert_entries):
    stack = []
    for entry in insert_entries:
        while stack and stack[-1] <= entry:
            stack.pop()
            # Do something with the popped item here
        stack.append(entry)

Way 1 : Traversing from end to start

Algorithm 1

This problem requires us to find the position of the first element greater than each element to its right, which is a typical application scenario for a monotonic stack.

We traverse the array temperatures from right to left, maintaining a stack stk that is monotonically increasing from top to bottom in terms of temperature. The stack stores the indices of the array elements.

For each element temperatures[i], we continuously compare it with the top element of the stack.

If the temperature corresponding to the top element of the stack is less than or equal to temperatures[i], we pop the top element of the stack in a loop until the stack is empty or the temperature corresponding to the top element of the stack is greater than temperatures[i].

At this point, the top element of the stack is the first element greater than temperatures[i] to its right, and the distance is stk.top() โˆ’ i.

We update the answer array accordingly. Then we push temperatures[i] onto the stack and continue traversing.

After the traversal, we return the answer array.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array temperatures.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []                                                  # Initialize an empty stack to store indices of temperatures.
        ans = [0]*n                                               # Initialize a result list with zeros.

        for i in range(n-1,-1,-1):
            while stk and temperatures[stk[-1]]<=temperatures[i]: #while the stack is not empty and the current temperature is greater than the temperature at the index on the top of the stack,
                stk.pop()                                         #Pop the stack.
            if stk:
                ans[i] = stk[-1]-i                                #Set the value in the result array at the top index of the stack to the difference between the current index and the top index of the stack
            stk.append(i)                                         #Push the current index onto the stack
        return ans                                                #Return the result array.

Way 2 : Traversing from start to end

Algorithm 2

We can also use a monotonically decreasing stack to find the next higher temperature.

We will use a stack to store the indices of the temperatures array.

We iterate over the array, and for each temperature, we check whether the current temperature is greater than the temperature at the index on the top of the stack.

If it is, we update the corresponding position in the result array and pop the index from the stack.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []
        ans = [0] * n
        for i in range(n):
            while len(stk) > 0 and temperatures[stk[-1]] < temperatures[i]:
                poped_idx = stk.pop(-1)
                ans[poped_idx] = i - poped_idx
            stk.append(i)
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = []                # a decreasing stack
        ans = [0]*n

        for i, v in enumerate(temperatures):
            while stk and temperatures[stk[-1]] < v:
                idx = stk.pop()
                ans[idx] = i-idx
            stk.append(i)
        return ans
equivalency 
stk.pop(-1)
    ||
    ||
    ||
stk.pop()
Algo dry run Corner 
i = 0 , v = 73
stk = [0]
ans = [0,0,0,0,0,0,0,0]

i = 1 , v =74
idx = 0
ans[idx] = i -idx
ans[0] = 1-0 = 1
stk = [1]

i = 2 , v = 75
idx = 1
ans[idx] = i - idx
ans[1] = 2-1 = 1
stk = [2]

i = 3 , v= 71

Approach:Monotonic Stack (Increasing)

Question

Follow up: Is it possible to solve this problem using increasing stack?

Answer: No. This problem cannot be solved by increasing stack from either direction. If increasing stack is used, then when a smaller element is met, the last element in the stack will be popped. Then the reference for the popped element is missed. Never will we know which element is its larger element.

Monotonic Stack Increasing template

Monotonic increasing stack

The same logic can be applied to maintain a monotonic queue.

def fn(arr):
    stack = []
    ans = 0

    for num in arr:
        # for monotonic decreasing, just flip the > to <
        while stack and stack[-1] > num:
            # do logic
            stack.pop()
        stack.append(num)

    return ans
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments