Daily Temperatures

Hash TableStack
https://leetcode.com/problems/daily-temperatures

# Solution

Let nn be the length of the array T and mm be the length of dct (<100< 100).

# Brute Force

Traverse the Temperature list in reverse order. For every element T[i], find the minimum index of temperatures from T[i]+1 to 100100 in dct.

Complexity

time: O(nm)O(nm)
space: O(m)O(m)

def dailyTemperatures(self, T: List[int]) -> List[int]:
    n = len(T)
    res = [0 for _ in range(n)]
    dct = dict()

    for i in reversed(range(n)):
        # the max of t is 101 b/c T[i] can be 100
        warmer_idx = min(dct.get(t, sys.maxsize) for t in range(T[i]+1, 102))
        if warmer_idx < sys.maxsize:
            res[i] = warmer_idx - i
        dct[T[i]] = i

    return res
1
2
3
4
5
6
7
8
9
10
11
12
13

# Monotonic Stack

stack stores the indices of T in descending order of temperature from bottom to top. While the current temperature is larger than the temperature at the top of the stack, pop the stack update index difference in res. At the end of the while loop, append the current index.

Complexity

time: O(n)O(n)
space: O(n)O(n)

def dailyTemperatures(self, T: List[int]) -> List[int]:
    n = len(T)
    stack = [0]
    res = [0 for _ in range(n)]


    for i in range(1, n):
        while stack and T[i] > T[stack[-1]]:
            idx = stack.pop()
            res[idx] = i - idx
        stack.append(i)

    return res
1
2
3
4
5
6
7
8
9
10
11
12
13