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!