Leetcode 739. Daily Temperatures

Explanation

The problem aims to find the number of days until we can experience a warmer day. In simpler terms, we need to return an array such that for each element, we provide how long in terms of number of days one needs to wait for a warmer day. If no such day is found, we need to return 0.

Starting from the last day, compare the current day with the top of the stack (which represents the next warmer day). If it is bigger, it means it is a warmer day and we have to update the list and all previous days that has lesser temperature.

In such a case, pop the current top of stack and use the next top to calculate days until the next warmer day. Then push the current day to top of stack. If the current day is less than or equal to the top of stack, push the current day to stack.

Walking through with an example: for the input [73, 74, 75, 71, 69, 72, 76, 73], the steps would go as follows:

• We start from 73. Since there is no element in the stack, push it into the stack.
• The next is 74. We pop 73 from stack and push 74 into it. The answer for 73 is 1.
• Similar process happens for 75. Also, since 74 and 75 have no warmer days later, we add 0 to their answers.
• Next, 71 and 69 are pushed to the stack.
• Then comes 72. We pop 69 from the stack and add 1 (72's index - 69's index) as 69's answer. 72 is pushed to the stack.
• Next, 76 causes popping of 72, 71 and 75 from stack and corresponding values are added to their answers.
• We continue this way till we go through all the elements in the original list.

Python Solution

1
2python
3class Solution:
4    def dailyTemperatures(self, T):
5        ans = [0] * len(T)
6        stack = [] # stack to keep track of the index of the temperatures
7        for i in range(len(T)):
8            while stack and T[i] > T[stack[-1]]:
9                index = stack.pop()
10                ans[index] = i - index
11            stack.append(i)
12        return ans

Java Solution

1
2java
3class Solution {
4    public int[] dailyTemperatures(int[] T) {
5        int[] result = new int[T.length];
6        Stack<Integer> stack = new Stack<>();
7        for(int i = 0; i < T.length; i++){
8            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
9                int index = stack.pop();
10                result[index] = i - index;
11            }
12            stack.push(i);
13        }
14        return result;
15    }
16}

Javascript Solution

1
2javascript
3var dailyTemperatures = function(T) {
4    let stack = [];
5    let result = new Array(T.length).fill(0);
6    for(let i = 0; i < T.length; i++) {
7        while(stack.length != 0 && T[i] > T[stack[stack.length-1]]) {
8            let index = stack.pop();
9            result[index] = i - index;
10        }
11        stack.push(i);
12    }
13    return result;
14};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> dailyTemperatures(vector<int>& T) {
6        stack<int> stack;
7        vector<int> result(T.size(), 0);
8        for(int i = 0; i < T.size(); i++){
9            while(!stack.empty() && T[i] > T[stack.top()]){
10                int index = stack.top();
11                stack.pop();
12                result[index] = i - index;
13            }
14            stack.push(i);
15        }
16        return result;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int[] DailyTemperatures(int[] T) {
5        int[] result = new int[T.Length];
6        Stack<int> stack = new Stack<int>();
7        for(int i = 0; i < T.Length; i++) {
8            while(stack.Any() && T[i] > T[stack.Peek()]){
9                int index = stack.Pop();
10                result[index] = i - index;
11            }
12            stack.Push(i);
13        }
14        return result;
15    }
16}

In these solutions, we use a stack to keep track of the indexes of the elements in the original array. This stack helps us remember the "unresolved" elements that we have seen so far, i.e., the elements for which we have not yet found a warmer day.

When we encounter a new temperature, we check if it is greater than the temperature at the index on top of the stack. If it is, that means we have found a warmer day for the element at the top of stack, so we pop its index from the stack, calculate the number of days until this warmer day (which is the current index minus the popped index), and update the answer at the popped index with this number of days.

We keep doing this while the new temperature is greater than the temperature at the top of the stack, meaning we resolve as many previous temperatures as we can before we move on to the next day. Once we have done that, we push the current index onto the stack. This means the stack will always contain a decreasing sequence of temperatures.

At the end, any indexes that are still left in the stack are temperatures for which we did not find any warmer day. The answer for these indexes remains 0, which was the original initialization.

This approach ensures that we visit each temperature only once, giving us a time complexity of O(n) where n is the number of temperatures. The auxiliary space complexity is also O(n) for the stack and the result array. In terms of spatial locality, this solution is efficient because it uses a stack -- a kind of container that promotes locality and thus, in theory, makes better use of cache memory.

The main idea of the solution is that, as we iterate through the temperatures, we are trying to find out, for each of them, how much longer we would need to wait for a warmer day. This is a next greater element problem, which is a classical problem which can be solved by iterating from right-to-left, while maintaining a stack of elements sorted in a decreasing order.

As for the languages, the solutions in Python, Java, JavaScript, C++, and C# share the exactly same logic, the difference being in how each language implements stacks and arrays. The use of a stack data structure is common across all these solutions. The languages that have built-in support for dynamic arrays (JavaScript, Python, and C#) make it easier to initialize the answer array, but the solutions in Java and C++ also handle this aspect efficiently.