125. Daily Temperatures
🔗 LeetCode Problem: 739. Daily Temperatures
📊 Difficulty: Medium
🏷️ Topics: Array, Stack, Monotonic Stack
Problem Statement
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation:
Day 0 (73°): Next warmer is day 1 (74°) → wait 1 day
Day 1 (74°): Next warmer is day 2 (75°) → wait 1 day
Day 2 (75°): Next warmer is day 6 (76°) → wait 4 days
Day 3 (71°): Next warmer is day 5 (72°) → wait 2 days
Day 4 (69°): Next warmer is day 5 (72°) → wait 1 day
Day 5 (72°): Next warmer is day 6 (76°) → wait 1 day
Day 6 (76°): No warmer day → 0
Day 7 (73°): No warmer day → 0
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
🌟 Understanding the Problem
What Are We Really Asking?
For each day, find how many days until a warmer temperature.
Example: [73, 74, 75, 71, 69, 72, 76, 73]
Day 0 (73°):
Look right: 74° (warmer!) on day 1
Days to wait: 1 - 0 = 1 ✓
Day 2 (75°):
Look right: 71°, 69°, 72° (not warmer)
: 76° (warmer!) on day 6
Days to wait: 6 - 2 = 4 ✓
Day 6 (76°):
Look right: 73° (not warmer)
Look right: nothing left
Days to wait: 0 ✓
Key Insight: We're finding the DISTANCE to the next greater element!
💡 Connection to Previous Problems
How is This Related to Next Greater Element?
┌─────────────────────────────────────────────────────────┐
│ NGE I/II │ Daily Temperatures │
├─────────────────────────────────────────────────────────┤
│ Find: Next greater │ Find: Next greater │
│ VALUE │ POSITION │
│ │ │
│ Return: The greater │ Return: Distance to │
│ value itself │ that position │
│ │ │
│ Example: │ Example: │
│ [1,3,4,2] → [3,4,-1,4] │ [73,74,75] → [1,1,0] │
│ (values) │ (distances) │
└─────────────────────────────────────────────────────────┘
The core pattern is IDENTICAL!
NGE: "What is the next greater element?"
DT: "How far is the next greater element?"
Both use the same "waiting elements" pattern!
💡 How to DISCOVER the Solution
Let me show you the natural thought progression.
🎯 STEP 1: Understanding "Days to Wait"
What does the answer mean?
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [ 1, 1, 4, 2, 1, 1, 0, 0]
For index 0:
Answer is 1
Meaning: 1 day later (index 0+1=1) is warmer
temperatures[1] = 74° > 73° ✓
For index 2:
Answer is 4
Meaning: 4 days later (index 2+4=6) is warmer
temperatures[6] = 76° > 75° ✓
For index 6:
Answer is 0
Meaning: No warmer day found
Pattern:
We're calculating: (position of next greater) - (current position)
🎯 STEP 2: First Attempt - What Would You Try?
Brute Force Thinking:
"For each day, scan right until I find a warmer day!"
for i in 0 to n-1:
for j in i+1 to n-1:
if temperatures[j] > temperatures[i]:
answer[i] = j - i
break
if no warmer found:
answer[i] = 0
Let's code this:
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
// Scan right for warmer day
for (int j = i + 1; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break;
}
}
// If inner loop completes, answer[i] stays 0
}
return answer;
}
Does it work?
Yes! ✓
But is it fast?
No! ❌
Time: O(n²)
For each element (n), scan remaining elements (up to n)
🎯 STEP 3: What's the Bottleneck?
The problem:
For each day, we're scanning ALL future days.
Example: [70, 71, 72, 73, 74, 75, 76]
Day 0: Scan 1,2,3,4,5,6 → find day 1 (1 scan)
Day 1: Scan 2,3,4,5,6 → find day 2 (1 scan)
Day 2: Scan 3,4,5,6 → find day 3 (1 scan)
...
We're repeating a LOT of work!
Question: Can we avoid rescanning?
🎯 STEP 4: The Key Observation
Think about this carefully:
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
When we're at 71 (index 3):
We need to find next warmer
When we're at 69 (index 4):
We need to find next warmer
Notice: Both 71 and 69 are WAITING for something warmer!
This is the same "waiting elements" pattern from NGE!
🎯 STEP 5: Can We Reuse the NGE Pattern?
From NGE, we learned:
Elements waiting for next greater → store in a stack!
When a larger element appears:
- Pop all smaller waiting elements
- Resolve them
But there's a KEY difference here:
NGE: Return the greater VALUE
answer[i] = temperatures[j] (the value itself)
Daily Temperatures: Return the DISTANCE
answer[i] = j - i (the difference in positions)
Question: What should we store in the stack?
🎯 STEP 6: Values or Indices? (Critical Decision!)
Let's think this through:
Attempt 1: Store temperature values
Stack: [73, 71, 69] ← These are VALUES
When we see 72°:
72 > 69? YES
Pop 69... but wait!
Problem: answer[?] = distance
Where was 69? What index?
WE DON'T KNOW! ❌
Attempt 2: Store indices
Stack: [3, 4] ← These are INDICES
(71°, 69°)
When we see 72° at index 5:
temperatures[4] = 69 < 72? YES
Pop index 4
answer[4] = 5 - 4 = 1 ✓
We have BOTH:
- Position (index 4)
- Value (temperatures[4])
Perfect! ✓
The answer: Store INDICES (not values)
Why?
1. We need the POSITION to calculate distance
2. We can get the VALUE from index: temperatures[index]
3. Indices give us both pieces of information!
🎯 STEP 7: The Algorithm Emerges
Based on NGE pattern + storing indices:
Initialize:
answer = array of zeros
stack = empty (stores indices)
Scan left to right:
For each day i:
current = temperatures[i]
While stack not empty AND temperatures[stack.top] < current:
prevDay = stack.pop()
answer[prevDay] = i - prevDay ← Distance!
stack.push(i) ← Store current index
Why this works:
1. Stack stores indices of days waiting for warmer weather
2. When warmer day arrives, pop and calculate distance
3. Stack maintains decreasing temperatures (like NGE)
🎯 STEP 8: Visual Walkthrough
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
indices = 0 1 2 3 4 5 6 7
═══════════════════════════════════════════════════════════
i=0, temp=73°
═══════════════════════════════════════════════════════════
Stack: []
Action: Push 0
Stack: [0] ← index 0 (73°) waiting
Answer: [0,0,0,0,0,0,0,0]
═══════════════════════════════════════════════════════════
i=1, temp=74°
═══════════════════════════════════════════════════════════
Stack: [0]
Check: temperatures[0]=73 < 74? YES!
Action: Pop 0
answer[0] = 1 - 0 = 1 ✓
WHY? Day 0 waits 1 day for warmer weather
Stack: []
Push: 1
Stack: [1] ← index 1 (74°) waiting
Answer: [1,0,0,0,0,0,0,0]
═══════════════════════════════════════════════════════════
i=2, temp=75°
═══════════════════════════════════════════════════════════
Stack: [1]
Check: temperatures[1]=74 < 75? YES!
Action: Pop 1
answer[1] = 2 - 1 = 1 ✓
WHY? Day 1 waits 1 day for warmer weather
Stack: []
Push: 2
Stack: [2] ← index 2 (75°) waiting
Answer: [1,1,0,0,0,0,0,0]
═══════════════════════════════════════════════════════════
i=3, temp=71°
═══════════════════════════════════════════════════════════
Stack: [2]
Check: temperatures[2]=75 < 71? NO
WHY NOT pop? 71 is COLDER than 75
75 is still waiting for warmer
Action: Push 3
Stack: [2, 3] ← 75° and 71° both waiting
Answer: [1,1,0,0,0,0,0,0]
Note: Stack maintains DECREASING order!
temperatures[2]=75 > temperatures[3]=71
═══════════════════════════════════════════════════════════
i=4, temp=69°
═══════════════════════════════════════════════════════════
Stack: [2, 3]
Check: temperatures[3]=71 < 69? NO
WHY? 69 is even COLDER
Action: Push 4
Stack: [2, 3, 4] ← 75°, 71°, 69° all waiting
Answer: [1,1,0,0,0,0,0,0]
Still decreasing: 75 > 71 > 69 ✓
═══════════════════════════════════════════════════════════
i=5, temp=72°
═══════════════════════════════════════════════════════════
Stack: [2, 3, 4]
Check: temperatures[4]=69 < 72? YES!
Action: Pop 4
answer[4] = 5 - 4 = 1 ✓
WHY? Day 4 (69°) waits 1 day for 72°
Stack: [2, 3]
Check: temperatures[3]=71 < 72? YES!
Action: Pop 3
answer[3] = 5 - 3 = 2 ✓
WHY? Day 3 (71°) waits 2 days for 72°
Stack: [2]
Check: temperatures[2]=75 < 72? NO
WHY STOP? 72 is still colder than 75
75 keeps waiting
Action: Push 5
Stack: [2, 5] ← 75° and 72° waiting
Answer: [1,1,0,2,1,0,0,0]
Observation: 72 resolved TWO waiting days (4 and 3)!
═══════════════════════════════════════════════════════════
i=6, temp=76°
═══════════════════════════════════════════════════════════
Stack: [2, 5]
Check: temperatures[5]=72 < 76? YES!
Action: Pop 5
answer[5] = 6 - 5 = 1 ✓
WHY? Day 5 (72°) waits 1 day for 76°
Stack: [2]
Check: temperatures[2]=75 < 76? YES!
Action: Pop 2
answer[2] = 6 - 2 = 4 ✓
WHY? Day 2 (75°) waits 4 days for 76°
Stack: []
Push: 6
Stack: [6] ← 76° waiting
Answer: [1,1,4,2,1,1,0,0]
Observation: 76 resolved TWO more days (5 and 2)!
═══════════════════════════════════════════════════════════
i=7, temp=73°
═══════════════════════════════════════════════════════════
Stack: [6]
Check: temperatures[6]=76 < 73? NO
WHY? 73 is colder than 76
Action: Push 7
Stack: [6, 7] ← 76° and 73° waiting
Answer: [1,1,4,2,1,1,0,0]
═══════════════════════════════════════════════════════════
End of Array
═══════════════════════════════════════════════════════════
Stack: [6, 7] ← These days never found warmer
answer[6] = 0 (already initialized)
answer[7] = 0 (already initialized)
Final Answer: [1,1,4,2,1,1,0,0] ✓
🎯 STEP 9: Why Does Stack Maintain Decreasing Order?
This is crucial to understand!
The invariant: Stack temperatures are always DECREASING (top to bottom)
Why?
When we see temperature T:
- We pop ALL temperatures < T
- Remaining temperatures are ≥ T
- We push T
- Stack is still decreasing!
Example:
Stack: [75, 71, 69] (decreasing)
New temp: 72
Pop 69 (69 < 72)
Pop 71 (71 < 72)
Can't pop 75 (75 > 72)
Push 72
Stack: [75, 72] (still decreasing!)
Why this property helps:
When a new temperature T comes:
- We know EXACTLY which days it resolves
- ALL days with temperature < T
- We pop them all in one sweep
- Efficient! ✓
🎯 STEP 10: Why Indices Solve Everything
Let's compare the two approaches:
┌─────────────────────────────────────────────────────────┐
│ Store Values │ Store Indices │
├─────────────────────────────────────────────────────────┤
│ Stack: [73, 71, 69] │ Stack: [0, 3, 4] │
│ │ │
│ When we see 72: │ When we see 72 at i=5: │
│ Pop 69 │ Pop index 4 │
│ answer[?] = ? │ answer[4] = 5-4 = 1 ✓ │
│ ↑ │ ↑ ↑ │
│ Don't know position! │ Position Distance │
│ │ │
│ To get position: │ To get temperature: │
│ Need extra HashMap │ temperatures[4] ✓ │
│ value → index │ │
│ Extra space O(n) ❌ │ No extra space ✓ │
└─────────────────────────────────────────────────────────┘
With indices, we get BOTH:
index = stack.pop() ← Position (for distance)
temp = temperatures[index] ← Temperature (for comparison)
Perfect! ✓
🎯 Approach 1: Brute Force
Implementation
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
// For each day
for (int i = 0; i < n; i++) {
// Scan forward for warmer day
for (int j = i + 1; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break;
}
}
// If no warmer day found, answer[i] stays 0
}
return answer;
}
Complexity Analysis
⏰ Time: O(n²)
Outer loop: n iterations
Inner loop: up to n iterations
Total: n × n = O(n²)
Worst case: Decreasing temperatures [100, 99, 98, ..., 30]
Each day scans all remaining days
💾 Space: O(1) - excluding output array
🎯 Approach 2: Monotonic Stack (Optimal)
The Strategy
1. Use stack to store INDICES (not values)
2. Stack maintains DECREASING temperatures
3. When warmer day arrives, pop and calculate distance
4. Each index pushed/popped at most once → O(n)
Why Stack? (Summary)
1. Need to track "waiting" days
2. Recent days checked first (LIFO)
3. When warmer arrives, resolve ALL colder days
4. Stack automatically maintains decreasing order
5. Indices give us both position and temperature
Implementation
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n]; // Defaults to 0
Stack<Integer> stack = new Stack<>(); // Stores indices
// Scan left to right
for (int i = 0; i < n; i++) {
// Pop all colder days - current day resolves them
while (!stack.isEmpty() &&
temperatures[stack.peek()] < temperatures[i]) {
int prevDay = stack.pop();
answer[prevDay] = i - prevDay; // Calculate distance
}
// Current day is waiting for warmer weather
stack.push(i);
}
// Days remaining in stack never found warmer day
// answer[index] stays 0 (already initialized)
return answer;
}
Line-by-Line Explanation
int[] answer = new int[n];
// Why array of zeros? Days with no warmer day return 0
// Java initializes arrays to 0 automatically
Stack<Integer> stack = new Stack<>();
// Why Stack<Integer>? We store INDICES (positions)
// Why not values? Need position to calculate distance
for (int i = 0; i < n; i++) {
// Why left to right? Building up waiting days progressively
// Same direction as NGE I
while (!stack.isEmpty() &&
temperatures[stack.peek()] < temperatures[i]) {
// Why while? Resolve ALL colder days (could be multiple)
// Why stack.peek()? Check most recent waiting day first
// Why temperatures[stack.peek()]? Get temperature at that index
// Why < temperatures[i]? Current day is warmer, can resolve
int prevDay = stack.pop();
// Pop the waiting day that's now resolved
answer[prevDay] = i - prevDay;
// Calculate distance: current position - previous position
// WHY: prevDay is the position, i is current position
stack.push(i);
// Current day hasn't found warmer yet, so it's waiting
// Store its INDEX so we can calculate distance later
Detailed Dry Run
Input: temperatures = [73, 74, 75, 71]
═══════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════
answer = [0, 0, 0, 0]
stack = []
═══════════════════════════════════════════════════════════
i=0, temperatures[0]=73
═══════════════════════════════════════════════════════════
While: stack.isEmpty()? YES, skip
Push: stack.push(0)
WHY? Day 0 is waiting for warmer day
State:
stack = [0]
answer = [0,0,0,0]
═══════════════════════════════════════════════════════════
i=1, temperatures[1]=74
═══════════════════════════════════════════════════════════
While: !stack.isEmpty() && temperatures[0] < 74?
TRUE && 73 < 74? TRUE ← Enter loop
Iteration 1:
prevDay = stack.pop() = 0
answer[0] = 1 - 0 = 1
WHY? Day 0 (73°) found warmer day at position 1
Loop check: stack.isEmpty()? YES, exit
Push: stack.push(1)
WHY? Day 1 is now waiting
State:
stack = [1]
answer = [1,0,0,0]
═══════════════════════════════════════════════════════════
i=2, temperatures[2]=75
═══════════════════════════════════════════════════════════
While: !stack.isEmpty() && temperatures[1] < 75?
TRUE && 74 < 75? TRUE ← Enter loop
Iteration 1:
prevDay = stack.pop() = 1
answer[1] = 2 - 1 = 1
WHY? Day 1 (74°) found warmer day at position 2
Loop check: stack.isEmpty()? YES, exit
Push: stack.push(2)
State:
stack = [2]
answer = [1,1,0,0]
═══════════════════════════════════════════════════════════
i=3, temperatures[3]=71
═══════════════════════════════════════════════════════════
While: !stack.isEmpty() && temperatures[2] < 71?
TRUE && 75 < 71? FALSE ← Don't enter
WHY? 71 is COLDER than 75, can't resolve
Push: stack.push(3)
WHY? Day 3 is waiting
State:
stack = [2, 3] ← Both waiting
answer = [1,1,0,0]
Note: Stack is decreasing: temps[2]=75 > temps[3]=71 ✓
═══════════════════════════════════════════════════════════
End of Loop
═══════════════════════════════════════════════════════════
Stack: [2, 3] ← Days 2 and 3 never found warmer
answer[2] = 0 (stays 0)
answer[3] = 0 (stays 0)
Final Answer: [1,1,0,0] ✓
Verification:
Day 0: 73° → 74° at day 1, wait 1 day ✓
Day 1: 74° → 75° at day 2, wait 1 day ✓
Day 2: 75° → no warmer day, 0 ✓
Day 3: 71° → no warmer day, 0 ✓
Complexity Analysis
⏰ Time: O(n)
WHY O(n) and not O(n²)?
For loop: n iterations
While loop inside:
- Might look like nested loop → O(n²)?
- But each index pushed ONCE
- Each index popped AT MOST ONCE
Total operations:
Pushes: n
Pops: n (at most)
Total: 2n = O(n) ✓
Amortized analysis:
Even though while loop is inside for loop,
total pops across ALL iterations = n
Average per iteration = n/n = 1
💾 Space: O(n)
Stack: O(n) worst case
When? Decreasing temperatures [100,99,98,...,30]
All indices stay in stack
Best case: O(1)
When? Increasing temperatures [30,40,50,...,100]
Stack only holds 1 element at a time
📊 Approach Comparison
┌────────────────────────────────────────────────────────┐
│ Approach 1 Approach 2 │
│ (Brute Force) (Monotonic Stack) │
├────────────────────────────────────────────────────────┤
│ Core Idea For each day, Track waiting days │
│ scan forward with stack │
│ │
│ Time O(n²) O(n) ✓ │
│ Rescans many Each day pushed/ │
│ times popped once │
│ │
│ Space O(1) O(n) │
│ No extra space Stack storage │
│ │
│ When to n < 100 Always! ✓ │
│ use Simple to code Production code │
└────────────────────────────────────────────────────────┘
🧪 Edge Cases
Edge Case 1: All Increasing
Input: [30, 40, 50, 60, 70]
Output: [1, 1, 1, 1, 0]
Each day finds warmer next day
Last day has no next day
Edge Case 2: All Decreasing
Input: [70, 60, 50, 40, 30]
Output: [0, 0, 0, 0, 0]
No day finds warmer weather
Stack keeps growing
Edge Case 3: Single Day
Input: [75]
Output: [0]
Only one day, no next day possible
Edge Case 4: Two Days Same Temperature
Input: [75, 75]
Output: [0, 0]
75 is NOT greater than 75
Both days return 0
Edge Case 5: Peak in Middle
Input: [60, 80, 70, 75, 65]
Output: [1, 0, 1, 0, 0]
Day 0: 60→80 at day 1, wait 1
Day 1: 80 is peak, no warmer, 0
Day 2: 70→75 at day 3, wait 1
Day 3: 75 has no warmer, 0
Day 4: 65 has no next, 0
⚠️ Common Mistakes
Mistake 1: Storing values instead of indices
// ❌ WRONG - Can't calculate distance
Stack<Integer> stack = new Stack<>();
stack.push(temperatures[i]); // Pushing VALUE
// When popping:
int temp = stack.pop(); // Have value, but not position!
answer[?] = ? // Can't calculate distance!
// ✓ CORRECT - Store indices
stack.push(i); // Push INDEX
// When popping:
int prevDay = stack.pop(); // Have position!
answer[prevDay] = i - prevDay; // Can calculate!
Mistake 2: Wrong comparison operator
// ❌ WRONG - Using <=
while (!stack.isEmpty() &&
temperatures[stack.peek()] <= temperatures[i]) {
// This would pop equal temperatures too!
// But same temp is NOT warmer!
}
// ✓ CORRECT - Use <
while (!stack.isEmpty() &&
temperatures[stack.peek()] < temperatures[i]) {
// Only pop when strictly less (colder)
}
Mistake 3: Forgetting to initialize answer array
// ❌ WRONG - Not initializing
int[] answer = new int[n];
// What if some days never find warmer?
// Need to return 0 for them!
// ✓ CORRECT - But actually Java does this!
int[] answer = new int[n]; // Defaults to 0 in Java ✓
// In other languages might need:
Arrays.fill(answer, 0);
Mistake 4: Not checking stack.isEmpty()
// ❌ WRONG - Might throw EmptyStackException
while (temperatures[stack.peek()] < temperatures[i]) {
stack.pop();
}
// ✓ CORRECT - Check isEmpty first
while (!stack.isEmpty() &&
temperatures[stack.peek()] < temperatures[i]) {
stack.pop();
}
Mistake 5: Calculating wrong distance
// ❌ WRONG - Absolute value
answer[prevDay] = Math.abs(i - prevDay);
// Why wrong? i is always > prevDay (we scan left to right)
// abs() is unnecessary and hides bugs
// ❌ WRONG - Reversed
answer[prevDay] = prevDay - i;
// This gives negative numbers!
// ✓ CORRECT
answer[prevDay] = i - prevDay;
// Current position - previous position = distance forward
🎯 Pattern Recognition
This pattern appears when:
- Find "next greater/smaller" element
- Calculate DISTANCE to that element
- Need to track "waiting" elements
- Process array left to right
Key Indicators:
- "How many days until..."
- "How far to the next..."
- "Distance to first element that..."
- "Wait time for..."
Similar Problems: - Next Greater Element I/II (LC 496, 503) - Stock Span Problem (LC 901) - Online Stock Span - Trapping Rain Water (LC 42) - Largest Rectangle in Histogram (LC 84)
📝 Quick Revision Notes
🎯 Core Concept
Find distance to next greater element using monotonic stack. Store indices (not values) to calculate distance. Stack maintains decreasing temperatures. When warmer day comes, pop and resolve ALL colder waiting days.
⚡ Quick Implementation
import java.util.Arrays;
import java.util.Stack;
class Solution {
public int[] dailyTemperatures(int[] a) {
int len = a.length;
// similar to NGE 1.
int[] res = new int[len];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < len; i++) {
if(stack.isEmpty()) {
stack.push(i);
} else if(a[stack.peek()] > a[i]) {
stack.push(i);
} else {
while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
int poppedIndex = stack.pop();
res[poppedIndex] = i - poppedIndex;
}
stack.push(i);
}
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(Arrays.toString(s.dailyTemperatures(new int[] {73,74,75,71,69,72,76,73})));
System.out.println(Arrays.toString(s.dailyTemperatures(new int[] {30,40,50,60})));
System.out.println(Arrays.toString(s.dailyTemperatures(new int[] {30,60,90})));
}
}
🔑 Key Insights
Why Indices?
Need: Position for distance calculation
Have: temperatures[index] for comparison
Result: index gives us BOTH!
The Pattern:
1. Scan left to right
2. Pop colder days (temperatures[stack.peek()] < current)
3. Calculate distance: current position - popped position
4. Push current index (it's now waiting)
5. Days in stack at end → answer stays 0
Time Complexity Proof:
Each index:
- Pushed once: O(n)
- Popped once: O(n)
Total: O(n) ✓
NOT O(n²) because total pops = n across ALL iterations!
Stack Invariant:
Temperatures in stack are ALWAYS decreasing (top to bottom)
Why? Pop all smaller before pushing new
Helps? Know exactly which days to resolve
🎪 Memory Aid
"Stack holds WAITING days (indices)"
"Warmer comes → pop COLDER → calculate DISTANCE"
"Left to right, push and pop!"
"Indices = position + temperature!" ✨
⚠️ Don't Forget
- Store indices, not values
- Compare:
temperatures[stack.peek()] < temperatures[i] - Calculate:
i - prevDay(current - previous) - Check
!stack.isEmpty()before peek/pop - Answer defaults to 0 (already done in Java)
🔗 Connection to NGE
Same core pattern, different return value:
NGE: Return the VALUE of next greater
DT: Return the DISTANCE to next greater
Both use monotonic stack with indices!
Happy coding! This is a perfect bridge between NGE and more complex stack problems! 🚀