Daily Temperatures — Day 69(Python)

Photo by Isaac Smith on Unsplash

Today’s question is a medium tagged question in Leetcode. It is a common question among tech interviewers. Let us look into the question.

739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

One of the easiest ways to solve this problem is by taking each number, running a loop to find a number that is greater than the current number, and then finding the difference between the indexes of both the numbers.

Let us look into the code snippet.

class HighTempFinder:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        output = [0 for i in range(len(T))]
        for i in range(len(T)):
            for j in range(i+1, len(T)):
                if T[j] > T[i]:
                    output[i] = j - i
                    break
        return output

Complexity analysis.

Time Complexity

In the worst-case scenario, if the given array is monotonically decreasing, then we will be running the loop for N² times. Hence the time complexity is O(N²), where N is the number of elements in the array.

Space Complexity.

We are not storing any intermediary results in any data structures, hence space complexity is O(1).

If we try to run this code on leetcode, we will get a time limit exceeded error. We would need to improve the time complexity. Can we try using any extra data structure to solve this problem?

We can improve the time complexity by making use of a stack. In the stack, we will be storing the temperature and its index in the input array. We can run the loop that starts from the end of the input array. Each time, we will compare the current temperature and the topmost temperature in the stack. If the current temperature is higher or equal to the topmost temperature in the stack, we will keep popping the values from the stack.

If the stack is empty, the output will be 0 for that temperature else we will be storing the difference of index between current temperature and topmost element in the stack.

class HighTempFinder:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack_temp = [(T[-1], len(T)-1)]
        output = [0 for i in range(len(T))]
        for i in range(len(T)-2, -1, -1):
            while stack_temp and T[i] >= stack_temp[-1][0]:
                stack_temp.pop()
            if stack_temp == []:
                output[i] = 0
                stack_temp.append((T[i], i))
            else:
                output[i] = stack_temp[-1][1] - i
                stack_temp.append((T[i], i))
        return output

Complexity analysis.

Time Complexity

The time complexity for this algorithm is O(N).

Space Complexity.

The space complexity for this algorithm is O(N).