Daily Temperatures DSA Solution - Monotonic Stack - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 4: Stack & Queue

Learning Outcome

After this lesson, you should be able to use a monotonic stack to resolve "next greater" style questions in one pass.

Problem Statement

Given daily temperatures, return an array where each value tells how many days you must wait for a warmer temperature. If there is no future warmer day, use 0.

Brute Force Approach

For each day, scan all later days until a warmer temperature is found.

This is clear, but in the worst case it costs O(n^2).

Optimized Approach

Keep a stack of indices whose warmer day has not been found yet. The stack is decreasing by temperature. When the current temperature is warmer than the temperature at the stack top, pop that index and fill its answer.

Exact Pseudocode

answer = array of zeroes
stack = empty stack of indices
for i from 0 to length(temperatures) - 1:
  while stack is not empty and temperatures[i] > temperatures[stack.top]:
    prev = pop stack
    answer[prev] = i - prev
  push i
return answer

Reference Code

class Solution:
    def dailyTemperatures(self, temperatures):
        answer = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                prev = stack.pop()
                answer[prev] = i - prev
            stack.append(i)

        return answer

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(), 0);
        stack<int> st;

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

        return answer;
    }
};

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                answer[prev] = i - prev;
            }
            stack.push(i);
        }

        return answer;
    }
}

Sample Dry Run

Complexity

Edge Cases

• Strictly decreasing temperatures produce all zeroes.
• Equal temperatures are not warmer.
• Single-day input returns [0].

Interview Checklist

• Store indices, not temperatures, so you can compute distance.
• Use >, not >=, because equal is not warmer.
• Leave unresolved days as zero.

FAQs

The stack keeps unresolved days in decreasing temperature order.

The answer requires the number of days waited, which is the current index minus the previous index.

Next greater element with a monotonic stack.

Tags

• dsa
• data structures and algorithms
• stack queue
• monotonic stack
• medium
• interview preparation