# 1D list

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

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi