Difficulty: MediumStack

Daily Temperatures

Problem in Plain English

Given each day temperature, return for every day how many days ahead the next strictly warmer temperature occurs, or 0 when no later day is warmer.

Problem Statement

Given an array of integers temperatures representing 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] == 0 instead.

Only a strictly warmer day counts: equal temperatures do not resolve a wait. For temperatures = [73,74,75,71,69,72,76,73] the answer is [1,1,4,2,1,1,0,0].

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

Examples

Example 1

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Day 0 waits 1 day for 74, day 2 waits 4 days for 76, and the last two days never see a warmer day.

Example 2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Each day is beaten by the very next day except the last, which waits for nothing.

Example 3

Input: temperatures = [30,60,90]
Output: [1,1,0]

Days 0 and 1 each wait exactly one day; day 2 has no warmer future day.

Example 4

Input: temperatures = [70]
Output: [0]

The only day has no later day to inspect, so its wait stays zero.

Example 5

Input: temperatures = [70,70,71,70]
Output: [2,1,0,0]

The equal day 1 does not resolve day 0. Day 2 at 71 resolves days 0 and 1 at distances 2 and 1. No later day is warmer than 71, and the final day has no future.

Intuition

A day waits for the first later temperature strictly above its own. In Example 1 day 2 at 75 ignores 71,69,72 until day 6 at 76, so it waits 4 days. Keep unresolved day indices together; their temperatures never increase from bottom to top. A new warmer day resolves the colder indices on top immediately, while equal days stay waiting. Indices, rather than temperatures alone, let us compute the waiting distance.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Each day can simply look ahead until it finds relief. From a fixed day we scan every later day in order and stop at the first strictly warmer one.

Step-by-Step Logic

Allocate n zero answers. For each day i, start j = i + 1 and inspect later days in increasing order; Example 1 starts with i = 0 and j = 1.
When temperatures[j] > temperatures[i], write j - i and break. Days 0 and 1 find 74 and 75 on the next day, so both answers become 1.
Otherwise advance j until a strictly warmer day appears or the array ends. Day 2 skips j = 3,4,5 at 71,69,72 and finds j = 6 at 76, giving 4.
Leave the answer zero if the search ends without success. Days 3,4,5 get 2,1,1; days 6 and 7 remain zero.
Return the completed array [1,1,4,2,1,1,0,0].

Why It Works

For a fixed i, j visits later days in increasing index order. Every skipped day has temperature at most temperatures[i]. Thus the first successful strict comparison gives the smallest possible later index, and j - i is exactly the required wait. If no comparison succeeds, no warmer future day exists and the initialized zero is correct. Applying this argument independently to every i produces the full answer.

Dry Run

Brute Force: variable states at each step
i / temperature	j transitions / comparisons	answer write	answer after day
0 / 73	1:74 > 73, break	answer[0]=1	[1,0,0,0,0,0,0,0]
1 / 74	2:75 > 74, break	answer[1]=1	[1,1,0,0,0,0,0,0]
2 / 75	3:71 -> 4:69 -> 5:72 -> 6:76, break	answer[2]=4	[1,1,4,0,0,0,0,0]
3 / 71	4:69 -> 5:72, break	answer[3]=2	[1,1,4,2,0,0,0,0]
4 / 69	5:72, break	answer[4]=1	[1,1,4,2,1,0,0,0]
5 / 72	6:76, break	answer[5]=1	[1,1,4,2,1,1,0,0]
6 / 76	7:73 -> 8:end	stays 0	[1,1,4,2,1,1,0,0]
7 / 73	8:end	stays 0	return [1,1,4,2,1,1,0,0]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

For n days, an all-equal array makes the inner loop inspect n(n - 1)/2 pairs, so worst-case time is O(n^2). Counters use O(1) auxiliary space excluding the required O(n) output array; including output, total extra storage is O(n). Output initialization costs O(n); there is no sorting or hidden search library.

Code

Solution.java

1class Solution {2    public int[] dailyTemperatures(int[] temperatures) {3        int n = temperatures.length;4        int[] answer = new int[n];5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (temperatures[j] > temperatures[i]) {8                    answer[i] = j - i;9                    break;10                }11            }12        }13        return answer;14    }15}

Hints

Hint 1

From each day the answer scans forward, so days still waiting form a natural to-do list kept in order.

Hint 2

A new warmer day resolves the most recent waiting colder days first; a colder or equal stack top blocks any warmer waiting days below it.

Hint 3

Keep waiting day indices on a stack: while the current temperature beats the indexed day on top, pop it and record the distance.

Edge Cases

Strictly falling temperatures such as [100,90,80]: nothing ever pops and every answer stays 0.
Strictly rising temperatures such as [30,40,50,60]: each day pops immediately and every answer except the last is 1.
All equal temperatures such as [70,70,70]: strict comparison never triggers, so every answer stays 0.
One day returns [0]; there is no later index.
A plateau before a rise, [70,70,71], returns [2,1,0]; both equal days remain pending until 71 arrives.
One late hot day can pop an entire stack; repeated pops are necessary to resolve all earlier colder days.

Common Mistakes and Interview Tips

Pushing temperatures instead of indices: without positions the wait distance i - prev cannot be computed.
Popping on >= instead of strictly >: equal days are not warmer, and popping them assigns answers that should stay 0.
Forgetting the answer array starts at 0: unresolved days need no handling only because zero already means "never warmer".
Using if instead of while: day 5 in Example 1 must pop both index 4 and index 3.
Calling the stack strictly decreasing: equal temperatures remain stacked, so its temperatures are non-increasing.
Interview check: justify linear time by counting total pushes and pops, and specify whether the output array is included in the space bound.

Key Takeaway

For next-greater style waits, keep unresolved indices on a monotonic stack so each arrival settles exactly the days it relieves.