Daily Temperatures - Video Solutions

Problem Overview: You receive an array where temperatures[i] represents the temperature on day i. For every day, compute how many days you must wait until a warmer temperature appears. If no warmer day exists, return 0 for that position.

Approach 1: Monotonic Stack (O(n) time, O(n) space)

The optimal solution uses a monotonic decreasing stack that stores indices of days whose warmer temperature hasn't been found yet. As you iterate through the array, compare the current temperature with the temperature at the index on top of the stack. If the current temperature is higher, you've found the next warmer day for that index. Pop the index and compute the distance currentIndex - previousIndex. Continue until the stack is empty or the top temperature is greater than or equal to the current one. Push the current index afterward.

This works because each index is pushed and popped at most once, keeping the algorithm linear. The stack maintains a decreasing sequence of temperatures, which guarantees that when a warmer day appears it resolves multiple previous days efficiently. This is a classic use of stack combined with the monotonic stack pattern commonly used in "next greater element" style problems.

Approach 2: Optimized Array Traversal (O(n) time, O(n) space)

Another strategy scans the array from right to left while using previously computed answers to skip unnecessary checks. Maintain a result array initialized with zeros. For each index i, jump forward using i + result[i] until you find a warmer temperature or reach the end. If temperatures[j] is warmer, store j - i. If not, keep jumping using previously stored answers.

This method avoids an explicit stack but still leverages the idea that future results are already computed. In practice, it behaves similarly to dynamic programming over an array. Each index is visited a limited number of times, keeping overall complexity linear. The approach is useful in languages where array operations are simple and predictable.

Recommended for interviews: The monotonic stack solution is the expected answer. Interviewers often use this problem to test whether you recognize the "next greater element" pattern and can apply a monotonic structure efficiently. Brute force reasoning (checking future days) demonstrates baseline understanding, but implementing the O(n) stack solution shows strong algorithmic pattern recognition.