739. Daily Temperatures

Problem

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

Explanation

I know there is a more optimized way to solve this with a monotonic stack in O(n), but this portfolio is where I document my own first passes and what helped me learn. Here I keep my original two-loop solution because it was the way I reasoned through the problem before discovering the optimized approach.

My approach: look ahead with nested loops

For each day i, I scan forward day by day until I find a warmer temperature. I track how many steps I move (counter). If I find a warmer day, I store that distance in solution[i]. If I reach the end without finding one, solution[i] stays 0. I added quick guards for empty and single-element inputs. This method is simple to read and matches how I first thought about the problem, even though it is less efficient than the stack-based solution.

Time: O(n^2) in the worst case (e.g., strictly decreasing temperatures)
Space: O(1) extra beyond the output array

Solution

Optimized approach I found (not mine)

This is the monotonic-stack solution I learned from a video (not my own idea). It runs in O(n) time by keeping indices in a stack that is strictly decreasing by temperature; when a warmer day appears, it resolves all cooler days on top of the stack.

class Solution {
	public int[] dailyTemperatures(int[] temperatures) {
		java.util.Stack<Integer> stack = new java.util.Stack<>();
		int[] result = new int[temperatures.length];
 
		for (int i = 0; i < temperatures.length; i++) {
			while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
				int idx = stack.pop();
				result[idx] = i - idx;
			}
			stack.push(i);
		}
 
		return result;
	}
}