739. Daily Temperatures

Naive O(n²) solution will get TLE.

Here is an improved version by using bisect after collecting all the indexes of temperatures.

36 / 37 test cases passed. TLEclass Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
temp_idx = collections.defaultdict(list)
for i, t in enumerate(T):
temp_idx[t].append(i)
res = []
for i, t in enumerate(T):
this_res = []
for key in range(t+1, 101):
j = bisect.bisect_right(temp_idx[key], i)
if j<len(temp_idx[key]):
this_res.append(temp_idx[key][j])
if this_res:res.append(min(this_res)-i)
else:res.append(0)
return res

Change the loose 101 bound the maxT+1, it works. The complexity of this algorithm is O(n*k log n)

class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
temp_idx = collections.defaultdict(list)
MAXT = 0
for i, t in enumerate(T):
MAXT = max(MAXT, t)
temp_idx[t].append(i)
res = []
for i, t in enumerate(T):
this_res = []
for key in range(t+1, MAXT+1):
j = bisect.bisect_right(temp_idx[key], i)
if j<len(temp_idx[key]):
this_res.append(temp_idx[key][j])
if this_res:res.append(min(this_res)-i)
else:res.append(0)
return res

A better one (the idea is similar to the monotonically queue)

class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
ans = [0] * len(T)
stack = []
for i, t in enumerate(T):
while stack and T[stack[-1]] < t:
prev_idx = stack.pop()
ans[prev_idx] = i - prev_idx
stack.append(i)
return ans

Data Scientist/MLE/SWE @takemobi