Problem

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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution

Method 1 - Brute Force

  • For each index i, iterate through the array to find the first index j where T[j] > T[i] or reach the array’s end.
  • If such a j is found, set ans[i] = j - i.
  • If no such j exists, set ans[i] = 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& T) {
        int n = T.size();
        std::vector<int> ans(n, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (T[j] > T[i]) {
                    ans[i] = j - i;
                    break;
                }
            }
        }

        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    ans[i] = j - i;
                    break;
                }
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n

        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    ans[i] = j - i
                    break

        return ans

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Monotonic Stack

We can maintain the stack in Monotonic decreasing order. 

We start from beginning of the array, and

  • push element on stack if it is smaller than previous pushed element on stack
  • pop elements from stack if current element is larger than element on stack
  • A decreasing monotonic will always maintain decreasing order of elements when considered from bottom-to-top.

The algorithm can be summarized as follows:

  1. Initialize an empty stack s and an array ans of size N (all initialized to 0).
  2. Iterate through the temperatures array temperatures.
  3. For each day curr, check if the current temperature temperatures[curr] is higher than the temperatures corresponding to the indices in the stack (temperatures[stk.top()]). If so, assign the answer for these indices and pop them from the stack.
  4. Push the current day curr onto the stack to find the next warmer day for curr.
  5. Any indices remaining in the stack at the end do not have a warmer future day, and their ans values remain 0, which is already initialized.

Note: We push the indices onto the stack to maintain the correct output format.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int n = temperatures.length;
        int[] ans = new int[n];
        
        for (int i = 0; i < n; i++) {
	        // if curr temperature is higher than one in stack
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = i - idx;
            }
            stack.push(i);
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(temperatures)
        
        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                idx = stack.pop()
                ans[idx] = i - idx
            stack.append(i)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Monotonic Stack Approach 2

Another intuitive way to approach the problem using a monotonic stack is by starting from the end of the array. This method maintains a monotonic stack similar to the previous approach, but iterates from the last element to the first.

The algorithm can be summarized as follows:

  1. Initialize an empty stack stk and an ans array of size N, all initialized to 0.
  2. Iterate over temperatures from the end.
  3. For each current day curr, pop elements from the stack that have temperatures(temperatures[stk.top()]) less than or equal to current or today’s temperature temperatures[curr]. These elements are popped as they are cooler and occur later than curr, thus they cannot be future answers for earlier days.
  4. After popping, the stack is either empty or has a warmer temperature than curr.
    • If the stack is empty, set ans[curr] = 0 as no warmer day exists.
    • Otherwise, set ans[curr] = stk.top() - curr, which is the difference between the indices of the next warmer day and curr.
  5. Then, push curr onto the stack as it may be the next closest warmer day for future days.
  6. Finally, return the ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                ans[i] = stack.peek() - i;
            }
            stack.push(i);
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []

        for i in range(n - 1, -1, -1):
            while stack and temperatures[stack[-1]] <= temperatures[i]:
                stack.pop()
            if stack:
                ans[i] = stack[-1] - i
            stack.append(i)

        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)