Daily Temperature

Practice Here

Stack Approach#

Traverse the array right-to-left and maintain a monotonic stack of indices. The stack always stores indices of temperatures in increasing order from top to bottom, so for each day i we pop all days that are not warmer than temperatures[i] — they can never be the "next warmer day" for i or any future day to the left. The first remaining element in the stack is the nearest warmer day, and its distance is stk.top() - i. This yields O(n) time because each index is pushed and popped at most once.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> stk;

        vector<int> res(n, 0);

        for(int i = n-1; i>=0;i--){
            if(stk.empty()){
                stk.push(i);
                res[i] = 0;
            }else{
                while(!stk.empty() && temperatures[i] >= temperatures[stk.top()]){
                    stk.pop();
                }

                if(stk.empty()){
                    res[i] = 0;
                }else{
                    res[i] = stk.top() - i;
                }

                stk.push(i);
            }
        }
        return res;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Deque Approach#

Identical logic to the stack approach, but using a deque and operating on its front rather than the top. Since only one end is ever accessed (push and pop both happen at the front), this is functionally a stack. The deque provides the same O(n) time guarantee but with slightly more overhead than a plain stack; prefer the stack version unless the problem demands access to both ends of the structure.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        deque<int> dq;

        vector<int> res(temperatures.size());

        for(int i=temperatures.size()-1;i>=0;i--)
        {
            if(dq.empty())
            {
                dq.push_front(i);
                res[i]=0;
            }else{
                while(!dq.empty() && temperatures[i] >= temperatures[dq.front()])
                {
                    dq.pop_front();
                }

                if(dq.empty())
                    res[i]=0;
                else
                    res[i] = dq.front()-i;
                dq.push_front(i);
            }
            
        }
        return res;
    }
};

Underlying Stack uses dequeue implementation. We only need one side operation -> stack can be used

Follow-up: Left-to-Right Traversal#

The right-to-left approach answers the question for day i while processing day i. But you can flip the direction entirely: iterate left to right and instead of computing the answer immediately, defer it — push unresolved indices onto the stack, and resolve them when a warmer day arrives.

Key idea: the stack holds a "waiting list" of days that haven't found their next warmer day yet. For each new day i, pop every index j from the stack where temperatures[i] > temperatures[j]. Day j's answer is i - j. Then push i to wait for its warmer day later.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> stk;  // indices awaiting their next warmer day

        for (int i = 0; i < n; i++) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                int j = stk.top(); stk.pop();
                res[j] = i - j;
            }
            stk.push(i);
        }
        return res;
    }
};

Time Complexity: O(n) — each index is pushed and popped at most once
Space Complexity: O(n)

Why this is cleaner: the right-to-left version has to check stk.empty() twice per iteration (once to decide the answer, once after popping). The left-to-right version resolves answers in the while loop naturally — indices that stay on the stack after the loop finishes have no warmer day, so their default value of 0 is already correct.