medium Daily Temperatures

Problem Statement

Given an array of integers temperatures representing daily temperatures, calculate how many days you have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

Examples

Example 1

• Input: temperatures = [70, 73, 75, 71, 69, 72, 76, 73]
• Output: [1, 1, 4, 2, 1, 1, 0, 0]
• Explanation: The first day's temperature is 70 and the next day's temperature is 73 which is warmer. So for the first day, you only have to wait for 1 day to get a warmer temperature. Hence, the first element in the result array is 1. The same process is followed for the rest of the days.

Example 2

• Input: temperatures = [73, 72, 71, 70]
• Output: [0, 0, 0, 0]
• Explanation: As we can see, the temperature is decreasing every day. So, there is no future day with a warmer temperature. Hence, all the elements in the result array are 0.

Example 3

• Input: temperatures = [70, 71, 72, 73]
• Output: [1, 1, 1, 0]
• Explanation: For the first three days, the next day is warmer. But for the last day, there is no future day with a warmer temperature. Hence, the result array is [1, 1, 1, 0].

Constraints:

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

Solution

To solve the problem efficiently, we use a monotonic decreasing stack. The idea is to go through the temperatures array from left to right. At each index, we compare the current temperature with the temperatures at the indices stored in the stack. The stack keeps indices of temperatures waiting for a warmer day. If the current temperature is greater than the temperature at the top of the stack, we found a warmer day for that previous index. So, we pop the index from the stack and record the difference in positions (i.e., number of days waited).

We keep doing this while the stack is not empty and the current temperature is warmer than the top element. Once we’ve processed all warmer temperatures, we push the current index onto the stack. This process continues until we reach the end of the array. Any index left in the stack does not have a warmer day ahead, so its value remains 0. The result array is filled accordingly. This approach works in O(n) time using a stack to track pending temperatures.

Step-by-Step Algorithm

1. Initialize data structures:

   • Create a Stack<Integer> to store indices of unresolved temperatures.
   • Create an integer array res of same length as temperatures and fill it with 0s.

2. Traverse the temperatures array:

   • Loop from i = 0 to temperatures.length - 1:

3. For each temperatures[i]:

   • While stack is not empty and temperatures[i] > temperatures[stack.peek()]:
     • Pop the index from the top of the stack → let’s call it idx.
     • This means temperatures[i] is the next warmer temperature for temperatures[idx].
     • Set res[idx] = i - idx, because we waited i - idx days for a warmer temperature.

4. After checking warmer conditions:

   • Push the current index i onto the stack (to wait for a warmer temperature in the future).

5. After the loop ends:

   • The res[] array contains the final result.
   • Return res.

Algorithm Walkthrough

Initial Setup:

• res = [0, 0, 0, 0, 0, 0, 0, 0]
• stack = []

Traverse the array:

• 🔹i = 0 → temperature = 70

  • Stack is empty → nothing to compare.
  • Push index 0 to stack → stack = [0]
  • res = [0, 0, 0, 0, 0, 0, 0, 0]

• 🔹 i = 1 → temperature = 73

  • Stack top → index 0 → temperature at index 0 is 70
  • Compare current temp 73 with temp at index 0 → 73 > 70
  • This means day 1 is warmer than day 0
    → Pop index 0
    → Calculate days waited: 1 - 0 = 1
    → Set res[0] = 1
  • Push index 1 to stack → stack = [1]
  • res = [1, 0, 0, 0, 0, 0, 0, 0]

• 🔹 i = 2 → temperature = 75

  • Stack top → index 1 → temperature at index 1 is 73
  • Compare current temp 75 with 73 → 75 > 73
  • So, day 2 is warmer than day 1
    → Pop index 1
    → Days waited: 2 - 1 = 1
    → Set res[1] = 1
  • Push index 2 → stack = [2]
  • res = [1, 1, 0, 0, 0, 0, 0, 0]

• 🔹 i = 3 → temperature = 71

  • Stack top → index 2 → temperature at index 2 is 75
  • Compare 71 < 75 → no warmer temp
  • Push index 3 → stack = [2, 3]
  • res = [1, 1, 0, 0, 0, 0, 0, 0]

• 🔹 i = 4 → temperature = 69

  • Stack top → index 3 → temperature at index 3 is 71
  • Compare 69 < 71 → not warmer
  • Push index 4 → stack = [2, 3, 4]
  • res = [1, 1, 0, 0, 0, 0, 0, 0]

• 🔹 i = 5 → temperature = 72

  • Stack top → index 4 → temperature = 69
    → Compare 72 > 69 → warmer day found
    → Pop index 4
    → Days waited: 5 - 4 = 1
    → Set res[4] = 1

  • New stack top → index 3 → temperature = 71
    → Compare 72 > 71 → warmer
    → Pop index 3
    → Days waited: 5 - 3 = 2
    → Set res[3] = 2

  • New stack top → index 2 → temperature = 75
    → Compare 72 < 75 → not warmer → stop

  • Push index 5 → stack = [2, 5]

• res = [1, 1, 0, 2, 1, 0, 0, 0]

• 🔹 i = 6 → temperature = 76

  • Stack top → index 5 → temperature = 72
    → Compare 76 > 72 → warmer
    → Pop index 5
    → Days waited: 6 - 5 = 1
    → Set res[5] = 1

  • New stack top → index 2 → temperature = 75
    → Compare 76 > 75 → warmer
    → Pop index 2
    → Days waited: 6 - 2 = 4
    → Set res[2] = 4

  • Stack now empty

  • Push index 6 → stack = [6]

  • res = [1, 1, 4, 2, 1, 1, 0, 0]

• 🔹 i = 7 → temperature = 73

  • Stack top → index 6 → temperature = 76
    → Compare 73 < 76 → not warmer
  • Push index 7 → stack = [6, 7]
  • res = [1, 1, 4, 2, 1, 1, 0, 0]

Final Stack:

• stack = [6, 7]
• No warmer days found for index 6 and 7 → leave res[6] and res[7] as 0

Final Output:

res = [1, 1, 4, 2, 1, 1, 0, 0]

Code

Here is how we can implement this algorithm:

import java.util.Arrays;
import java.util.Stack;

public class Solution {

  public int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>(); // Initialize a stack to store indices of temperatures.
    int[] res = new int[temperatures.length]; // Initialize a result array.

    for (int i = 0; i < temperatures.length; i++) {
      while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
        // While the stack is not empty and the current temperature is higher
        // than the temperature at the index stored at the top of the stack:
        int idx = stack.pop(); // Pop the top index from the stack.
        res[idx] = i - idx; // Calculate the number of days until warmer temperature.
      }
      stack.push(i); // Push the current index onto the stack.
    }
    return res;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] temperatures1 = { 70, 73, 75, 71, 69, 72, 76, 73 };
    int[] temperatures2 = { 73, 72, 71, 70 };
    int[] temperatures3 = { 70, 71, 72, 73 };
    System.out.println(
      Arrays.toString(solution.dailyTemperatures(temperatures1))
    ); // Output: [1, 1, 4, 2, 1, 1, 0, 0]
    System.out.println(
      Arrays.toString(solution.dailyTemperatures(temperatures2))
    ); // Output: [0, 0, 0, 0]
    System.out.println(
      Arrays.toString(solution.dailyTemperatures(temperatures3))
    ); // Output: [1, 1, 1, 0]
  }
}

Complexity Analysis

Time Complexity:

Where n is the number of elements in the temperatures array.

• Every index i is pushed exactly once onto the stack.
• Every index is popped at most once.
• The while loop might look nested, but the total number of stack operations across the whole loop is — each element is pushed and popped once.

So, we do work even though there’s a loop inside a loop. It’s efficient due to the monotonic stack.

Space Complexity:

• The stack can hold up to n elements in the worst case (if the temperatures keep going down).
• The result array res[] also uses space.

So total space is due to:

• the stack, and
• the output array.