Problem Statement

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.

Examples

Solution

Points of Interest

Before we look for a solution let’s look at what properties we can find.

1. In an increasing sub-array, the next warmer day for each element, except for last one, is the next day. For instance, in [2,3,4] 2->3, 3->4
2. For a non-increasing sub-array, the next warmer day for each element can be only after this sub-array, where non-increasing trend breaks. For instance, in [4, 3, 2, 3.5], (3, 2) -> 3.5, but for 4 there is no warmer day.

Algo

We can use monotonic stack approach to solve this problem.

1. Initialize an empty stack, representing the pointers to array elements that are yet to be assigned next warmer day.
2. Initialize result array of length N, and all values set to 0. This signifies that their next warmer day is not found yet.
3. Iterate over elements of the array.
   1. Run a loop while stack is not empty and stack top element is less than current value in iteration, and internally keep popping elements from stack and assigning difference in days from current to the element popped, in the results.
   2. Outside above while loop, append current element pointer in the stack.

Code

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    stack = list()
    result = [0 for _ in temperatures]
    for i in range(len(temperatures)):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            oi = stack.pop()
            result[oi] = (i - oi)
        stack.append(i)
    return result

Complexity

$\textbf{Time Complexity} = O(N)$

• The outer loop visits each element of array only once.
• Inner loop pops stack values, each element once.
• Combination of these might seem $O(N^2)$, but inner loop is running only once for each element.

$\textbf{Space Complexity} = O(N)$

• We can have max N size of stack, when whole array is non-increasing
• Result array has N length