Problem 739

(Last updated: )

Question 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.

Solution

Certainly one could do an O($n^2$) solution by checking for each temperatures[i], the first instance of a future temperatures[j] for which we have temperatures[j]>temperatures[i]. However, the length of the temperature array can be as large as $10^5$, which would theoretically mean $10^{10}$ computations, and ain’t nobody got time for that.

So, we need to optimize this. This is where I think the hint provided in the question is particularly misleading. The hint reads: “If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, …, 99, or 100. We could remember when all of them occur next.”

Main idea 1:

The natural interpretation is to create a dictionary in O(n) time that stores for each temperature value, the indices in which the value occurs. Then for each index i of temperatures, we loop over values possibilities j = temperatures[i]+1 – 100, and scan the dictioinary values at j for an index k that is closest to i, and then minimize this k over all j. Certainly then the answer at index i will be k-i. This might end up being O($n^2$) also in the worst case if the dictionary values at j gets really long, even if the values are stored as a hashed object. But on average one would expect O(n) runtime.

This however, still turned out to be too slow. Then looking at the discussion section, I noticed a lot of people indicating the possibility of a stack based solution. That’s when it clicked how we can approach the problem in O(n) time using a montonic stack

Main idea 2:

Create a stack array initialized with 0, and a pointer value that runs through the temperatures array, initialized at 1. If temperatures[pointer] > temperatures[stack[-1]], then we have found the next warmest day, so we update answer[stack[-1]] with pointer - stack[-1] and pop the last element from the stack, if stack is non-empty after popping, then we check again if temperatures[pointer] > tempeartures[stack[-1]], and continue this way until either the stack is empty or this condition fails (i.e, the current day is colder than the last remaining day on the stack). If at any point, temperatures[pointer] is $\leq$ temperatures[stack[-1]] we don’t pop anything. Finally we append pointer to stack, and increase pointer by 1. Then we repeat this way until the pointer has marched all the way to the end of the temperatures list.

Here’s an example to see this in action

Suppose temperatures = [73,74,75,71,69,72,76,73]

Stack = [0], pointer = 1, ans after all computations for this stack config = [1,0,0,0,0,0,0,0]
Stack = [1], pointer = 2, ans after all computations for this stack config = [1,1,0,0,0,0,0,0]
Stack = [2], pointer = 3, ans after all computations for this stack config = [1,1,0,0,0,0,0,0]
Stack = [2,3], pointer = 4, ans after all computations for this stack config = [1,1,0,0,0,0,0,0]
Stack = [2,3,4], pointer = 5, ans after all computations for this stack config = [1,1,0,0,0,0,0,0]
Stack = [2,3], pointer = 5, ans after all computations for this stack config = [1,1,0,0,1,0,0,0]
Stack = [2], pointer = 5, ans after all computations for this stack config = [1,1,0,2,1,0,0,0]
Stack = [2,5], pointer = 6, ans after all computations for this stack config = [1,1,0,2,1,1,0,0]
Stack = [2], pointer = 6, ans after all computations for this stack config = [1,1,4,2,1,1,0,0]
Stack = [6], pointer = 7, ans after all computations for this stack config = [1,1,4,2,1,1,0,0]

Final ans = [1,1,4,2,1,1,0,0]

This runs in O(n) time, since we visit each index exactly once.

Code:

Main idea 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def dailyTemperatures2(self, temperatures: List[int]) -> List[int]:
    ans = [0 for _ in range(len(temperatures))]
    dic = defaultdict(set)
    for i in range(len(temperatures)):
        dic[temperatures[i]].add(i)

    for cur_index in range(len(temperatures)):
        closest_index = len(temperatures)
        for j in range(temperatures[cur_index]+1,101):
            if(not dic[j]):
                continue
            for k in dic[j]:
                if(k-cur_index >= 0 and k <= closest_index):
                    closest_index = k

        if(closest_index == len(temperatures)):
            ans[cur_index]=0
        else:
            ans[cur_index] = closest_index-cur_index
    return ans

Main idea 2:

1
2
3
4
5
6
7
8
9
10
11
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    ans = [0 for _ in range(len(temperatures))]
    stack = [0]
    pointer = 1
    while pointer<len(temperatures):
        while(stack and temperatures[pointer] > temperatures[stack[-1]]):
            ans[stack[-1]] = pointer - stack[-1]
            stack.pop()
        stack.append(pointer) 
        pointer+=1
    return ans

Comments:

Time complexity for main idea 1: O(n)-ish on average, O($n^2$) on a bad day
Time complexity for main idea 2: O(n) for any day

At the time of submission, the main idea 1 TLEs, and main idea 2 passes leetcode submission cases in 933ms, beats 51.02% of users. It uses 31.16MB of memory, beating 74.70% of users.