739. Daily Temperatures

Hello, reader 👋🏽 ! Welcome to day 78 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 739. Daily Temperatures.

🤔 Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days 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.

E.g.:

temperatures = [73,74,75,71,69,72,76,73]
=> [1,1,4,2,1,1,0,0]

temperatures = [30,40,50,60]
=> [1,1,1,0]

💬 Thought Process - Monotonic Stack

The naive way to solve would be to find the first greater temperature temperature[j] > temperature[i] for every i from 0 to n-1 such that i < j.
- Hence, we would have two loops: one for i from 0 to n-1, and the inner loop for index j from i+1 to n-1.
- The moment we find a temperature[j], we will stop the search and use j-i as the days difference for the next warmer temperature[i].
- But this solution takes O(n^2) in the worst case and we could do better.
The first thing to notice is that we need some data structure that holds the greatest temperatures seen so far.
And the second observation is that since we have to find the next greater temperature for every index i, it would be beneficial to traverse the temperatures array from n-1 to 0.
Now to look into the data structure, let's look at this idea. We need to have a list of all the greatest temperatures we have seen so far.
We could use something like a heap/ priority queue that holds the greatest temperatures sorted by indices.
- But heaps/ priority queues would take O(nlogn). Can we do better? The answer is Yes.
We could use a stack to hold these values such that the stack is monotonic. This means that the stack would only hold the greatest temperatures seen so far.
Hence as we traverse temperatures from the last index, we would compare current temperature temperatures[i] with the top element of the stack, stack[top].
- If the stack is empty => there was no temperature greater than temperatures[i] seen before
- If the stack[top] > temperatures[i] => then the number of days would be the j - i, where j is the index for the temperature of stack[top]
- If the stack[top] <= temperatures[i] => then we would have to repeatedly keep popping from the stack until:
  1. stack is empty, then number of days for next warmer temperature is 0.
  2. stack[top] > temperatures[i], then the number of days would be the j - i, where j is the index for the temperature of stack[top]
After we have found the answer for the current temperature, we will push the temperatures[i] into the stack since there could be a smaller temperature in the array.
Also note that since we have to compare the indices, it makes sense to add the index rather than the current temperature. Then we could compare temperature[i] with temperature[stack[top]].

👩🏽‍💻 Solution - Monotonic Stack

Below is the code for the approach for solving this problem using a monotonic stack.

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        if(temperatures == null || temperatures.length == 0) {
            return new int[0];
        }

        int n = temperatures.length;
        int[] warmerDaysWait = new int[n];

        Stack<Integer> warmerDayIndices = new Stack();

        for(int i = n-1; i >= 0; i--) {
            int temperature = temperatures[i];

            if(warmerDayIndices.isEmpty()) {
                warmerDaysWait[i] = 0;
            }
            else {
                while(!warmerDayIndices.isEmpty()) {
                    int topIndex = warmerDayIndices.peek();
                    if(temperature >= temperatures[topIndex]) {
                        warmerDayIndices.pop();
                    }
                    else {
                        break;
                    }
                }

                if(warmerDayIndices.isEmpty()) {
                    warmerDaysWait[i] = 0;
                }
                else {
                    warmerDaysWait[i] = warmerDayIndices.peek() - i;
                }
            }

            warmerDayIndices.push(i);
        }

        return warmerDaysWait;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

You can find the link to the GitHub repo for this question here: 739. Daily Temperatures.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian