Daily Temperatures
Mahabharata — Waiting for the Warmer Day — How Many Days Until a Hotter Battle?
आजस्य उत्तापात् अधिकः कदा आयास्यति?। प्रतीक्षया दिनानि गणय — उत्तरं स्वयमेव स्पष्टम्॥
*When will a day hotter than today arrive? Count the days of waiting — the answer reveals itself.*
The Story
Given an array of daily temperatures, return an array where each element is the number of days you have to wait until a warmer temperature. If no warmer day exists, use 0.
For `temperatures = [73,74,75,71,69,72,76,73]`: Answer: `[1,1,4,2,1,1,0,0]`
Arjuna tracked the war's intensity day by day. For each day, he wanted to know: "How many days until a more intense battle?"
This is the same **monotone stack** pattern as st-4, but instead of storing the NEXT GREATER VALUE, we store the NUMBER OF DAYS UNTIL that warmer day.
**Algorithm — monotone decreasing stack of indices:** - Stack holds INDICES with decreasing temperatures - When temperatures[i] > temperatures[stack.top]: pop the index j and record `res[j] = i - j`
Trace `[73,74,75,71,69,72,76,73]`: - i=0(73): push 0. stack=[0] - i=1(74): 73<74 → pop 0, res[0]=1-0=1. push 1. stack=[1] - i=2(75): 74<75 → pop 1, res[1]=2-1=1. push 2. stack=[2] - i=3(71): 75>71. push 3. stack=[2,3] - i=4(69): 71>69. push 4. stack=[2,3,4] - i=5(72): 69<72→pop 4, res[4]=5-4=1. 71<72→pop 3, res[3]=5-3=2. 75>72. push 5. stack=[2,5] - i=6(76): 72<76→pop 5, res[5]=6-5=1. 75<76→pop 2, res[2]=6-2=4. push 6. stack=[6] - i=7(73): 76>73. push 7. stack=[6,7] - End: res[6]=0, res[7]=0
Result: `[1,1,4,2,1,1,0,0]` ✓
"The answer is just the INDEX DIFFERENCE," Arjuna realized. "st-4 stored the value; st-5 stores the distance. Same stack mechanics, different answer.
Arjuna's Day-by-Day Search
For each day, scan forward until finding a warmer temperature. Record the distance. O(n²).
public int[] dailyTemperaturesBruteForce(int[] temperatures) {
int[] res = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++)
for (int j = i+1; j < temperatures.length; j++)
if (temperatures[j] > temperatures[i]) { res[i] = j-i; break; }
return res;
}The Monotonic Stack Distance Wisdom
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
int j = stack.pop();
res[j] = i - j; // Days waited
}
stack.push(i);
}
return res; // Remaining stack indices keep res[j]=0
}Step-by-Step Walkthrough
[73,74] → expected [1,0] i=0: push 0. stack=[0] i=1: 73<74 → pop 0, res[0]=1-0=1. push 1. stack=[1] End: stack=[1], res[1]=0 Return [1,0] ✅
Deep Insight
**st-4 vs st-5 comparison:** - st-4: `res[pop] = current_VALUE` (the next greater value itself) - st-5: `res[pop] = current_INDEX - popped_INDEX` (days waited) Same stack mechanics, different answer extraction.
**Why elements in the final stack get 0?** They never found a warmer day. The array initialized to 0 handles this automatically.
**Generalization:** The monotone stack pattern solves a class of "next greater/smaller" problems in O(n) that would otherwise require O(n²). The stack maintains the invariant that deeper elements are "waiting" for a qualifying event from later in the array.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Linear scan per day |
| Optimal | O(n) | O(n) | Each index pushed and popped at most once |
Pattern Recognition
✅ For each element: number of steps to next greater ✅ Monotone stack of indices (decreasing values) ✅ Pop when current > top: res[top] = i - top ✅ Remaining stack: answer stays 0 **LeetCode Trigger Phrases:** → "daily temperatures" → "days until warmer" → "how many steps to next greater" → monotone stack
Bhagavad Gita 2.22
वासांसि जीर्णानि यथा विहाय नवानि गृह्णाति नरोऽपराणि। तथा शरीराणि विहाय जीर्णान्यन्यानि संयाति नवानि देही॥
Just as a person puts on new garments giving up old ones, similarly, the soul accepts new material bodies, giving up the old and useless ones.
Connection: Each day in the stack waits for a warmer, more intense day to arrive — just as the soul waits for its next body. When that warmer day finally comes, the waiting days are 'resolved' and released from the stack, their waiting distance recorded. Like the soul that ultimately transcends each old form for a new one, each element in the stack is eventually superseded — or, if not (remaining in stack), accepts that no warmer day (no newer form) awaits.