Daily Temperatures medium

Problem Statement

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] as 0.

Example 1

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

Example 2

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

Steps

1. Initialize the result array: Create an array answer of the same size as temperatures, filled with zeros. This will store the waiting days for each temperature.

2. Use a stack: A stack will be used to store the indices of days, not the temperatures themselves. This is crucial for efficiently finding the next warmer day. The stack will maintain a decreasing order of temperatures.

3. Iterate through the temperatures: For each temperature temperatures[i]:

   • While the stack is not empty and the temperature at the top of the stack is less than the current temperature:
     • This means we've found a warmer day!
     • Pop the index top from the stack.
     • Calculate the waiting days: answer[top] = i - top.
   • Push the current index i onto the stack.

4. Return the result: After iterating through all temperatures, the answer array will contain the waiting days for each day.

Explanation

The stack maintains a decreasing order of temperatures. When we encounter a warmer temperature, we can pop elements from the stack until we find a warmer temperature or the stack is empty. The difference between the current index and the popped index represents the number of days to wait for a warmer temperature. If the stack is empty after processing a temperature, it means there is no warmer temperature in the future for that day.

Code

#include <vector>
#include <stack>

using namespace std;

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> answer(n, 0); // Initialize with 0s
    stack<int> s; // Stack to store indices

    for (int i = 0; i < n; ++i) {
        while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
            int top = s.top();
            s.pop();
            answer[top] = i - top;
        }
        s.push(i);
    }

    return answer;
}

Complexity

• Time Complexity: O(N), where N is the length of the temperatures array. Each element is pushed and popped at most once from the stack.
• Space Complexity: O(N) in the worst case, if the stack needs to store all indices. In the best case, the space complexity can be O(1) if the input array is already in increasing order.