Wait Time Until a Higher Temperature Arrives
Solve this Problemtemps, find, for every day, how many days it takes until a strictly warmer day arrives — or 0 if it never warms up again before the record ends.
This is the "next greater element" pattern, but asking for the distance to the answer instead of the value itself. A monotonic decreasing stack of day indices (not temperatures) makes the distance trivial to compute: whenever a warmer day arrives, every colder day still waiting on the stack gets popped, and its wait time is simply the gap between the current day's index and the popped day's index. Every day enters and leaves the stack at most once, giving O(n) total work instead of the brute force's O(n²) repeated scanning.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ temps.length ≤ 15 - ◆
30 ≤ temps[i] ≤ 100
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan Forward for Each Day
BruteFor every day i, scan forward day by day until a strictly warmer reading shows up, and record how many days that took. If no warmer day ever appears before the end of the record, the wait is 0. This checks every (day, later-day) pair directly — O(n) per day, O(n²) overall.
O(n²)O(n)1class Solution {
2 public int[] daysUntilWarmer(int[] temps) {
3 int n = temps.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 for (int j = i + 1; j < n; j++) {
7 if (temps[j] > temps[i]) {
8 result[i] = j - i;
9 break;
10 }
11 }
12 }
13 return result;
14 }
15}Optimal — Monotonic Decreasing Stack of Day Indices
OptimalKeep a stack of day indices whose temperatures are strictly decreasing from bottom to top. When a new, warmer day arrives, every colder day still waiting on the stack has just found its answer — pop each one and record the day-gap (current index minus the popped index) as its wait time — then push the current day. Every day is pushed once and popped at most once, so the total work across the whole record is O(n).
O(n)O(n)1class Solution {
2 public int[] daysUntilWarmer(int[] temps) {
3 int n = temps.length;
4 int[] result = new int[n];
5 Deque<Integer> stack = new ArrayDeque<>();
6 for (int i = 0; i < n; i++) {
7 while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
8 int idx = stack.pop();
9 result[idx] = i - idx;
10 }
11 stack.push(i);
12 }
13 return result;
14 }
15}