Description

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.

Example 1:

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

Example 2:

1Input: temperatures = [30,40,50,60]
2Output: [1,1,1,0]

Example 3:

1Input: temperatures = [30,60,90]
2Output: [1,1,0]

Constraints:

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

Solution:

The problem has given list of daily temperatures. The goal is to find the number of days after which you will get temperature greater than current day. Notice that on the last day, because there is no next temperature for i+1th day, you will always get number of days 0 for the last day.

Brute Force

In brute force approach, you can iterate through the array for each element and check the next available temperature which is higher than current one. While traversing, also keep track of number of days you had to traverse in order to find the number of days for ith day. You repeat this operation for all elements of the array.

 1class Solution {
 2    public int[] dailyTemperaturesBrute(int[] temperatures) {
 3        int[] result = new int[temperatures.length];
 4
 5        for (int i = 0; i < temperatures.length; i++) {
 6            int numDays = 0;
 7            for (int j = i + 1; j < temperatures.length; j++) {
 8                if (temperatures[j] > temperatures[i]) {
 9                    numDays = j - i;
10                    break;
11                }
12            }
13            result[i] = numDays;
14        }
15        return result;
16    }
17}

Using Monotonic Stack

Monotonic stacks can be a great option if we have a problem where ordering is important.

When iterating over input array of temperatures, we can push each temperature into a stack. When we move to the next element, at that point we will be calculating number of days for the previous day. In order to do that, we can insert index position of each day into the stack rather than temperatures. This way to find the number of days, we will have to pop each tempeture until we find a temperature that is smaller than current one. This way we will have to find the difference between those two indices to find the number of days.

 1
 2class Solution {
 3    public int[] dailyTemperatures(int[] temperatures) {
 4        int[] result = new int[temperatures.length];
 5        Stack<Integer> stack = new Stack<>();
 6
 7        for (int current = 0; current < temperatures.length; current++) {
 8            while (!stack.isEmpty() && temperatures[current] > temperatures[stack.peek()]) {
 9                int previous = stack.pop();
10                result[previous] = current - previous;
11            }
12            stack.push(current);
13        }
14        return result;
15    }
16}
  • Time Complexity: Each element can be added to the stack only once. So, this algorithm gives time complexity of O(n) even though there is inner while loop.
  • Space Complexity: At most, we may need to store all elements of the input array into stack which might give worst case time complexity of O(n)