See all coding puzzles and patterns here.

Problem Definition

Given an array of integer temperatures, where each value represents the daily temperature, return an array of integers representing how many days later the temperature is higher than the current temperature. For days with temperatures that are never hit again, return 0.

Examples

Some test cases to verify our solution.

assert days_to_temp([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
assert days_to_temp([30,40,50,60]) == [1,1,1,0]
assert days_to_temp([30,60,90]) == [1,1,0]
assert days_to_temp([8,1,5,4,1,2,1,1,0,0]) == [8,1,5,4,3,2,1,1,0,0]

Solution

This problem can be solved using a stack.

We'll initialize our answer with 0 values.

We'll keep a stack of temperatures and their indices that need hits. We'll iterate through the array of temperatures and compare the temperature to the value at the top of the stack. If the value is greater than or equal to the temperature at the top of the stack, then we'll pop values off the stack until the top value is less than the current temperature or the stack is empty.

For each popped value, we'll update the answer value for that index with the difference between the current index and the index in the stack. 

import math

DEFAULT_VAL = 0

def days_to_temp(temps: list[int]) -> list[int]:
    ans = [DEFAULT_VAL] * len(temps)
    # Items of form (index, temp)
    stack = []
    for i, temp in enumerate(temps):
        if stack:
            while stack and stack[-1][1] <= temp:
                prev_idx, prev_temp = stack.pop()
                ans[prev_idx] = i - prev_idx
        stack.append((i, temp))
    return ans

Complexity

Let $n = $ len(temps).

Runtime complexity should be $\Theta(n)$ since we are iterating over all of temps.

Auxiliary space complexity should be $\Theta(n)$, since in the worst case we will have up to $n-1$ items in our stack.