Definition
- Daily Temperatures – a monotonic stack problem that computes, for each day, how many days until a strictly warmer temperature.
- Index stack – store indices rather than values because the answer is the distance in positions, not the warmer value.
- Decreasing stack – the stack holds indices whose temperatures decrease from bottom to top, so the top is always the coldest pending day.
- Resolution – when a warmer day arrives, pop each colder index and set
answer[poppedIndex] = currentIndex - poppedIndex. - Complexity – O(n) time and O(n) space; each index is pushed and popped at most once.
Priya tracks a daily market sentiment score at National Bank of India and wants to know, for each day, how many days she waited until sentiment rose above that day's level. She keeps a pile of pending day numbers. When a higher-score day arrives, it resolves every pending day on top, and the answer is today minus that day. Days left on the pile at the end never saw a higher score, so their wait is zero.
Understanding the Concepts
What is the Daily Temperatures problem?
Given an array of temperatures, return an array where each position holds the number of days until a strictly warmer day. If no warmer day exists, the answer is 0. This is the Next Greater Element pattern, but the answer is the distance rather than the value.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class DailyTemperatures {
public static int[] dailyTemperatures(int[] temps) {
int[] answer = new int[temps.length];
Deque<Integer> stack = new ArrayDeque<>(); // indices
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
int prev = stack.pop();
answer[prev] = i - prev;
}
stack.push(i);
}
return answer;
}
public static void main(String[] args) {
int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
System.out.println(Arrays.toString(dailyTemperatures(temps)));
}
}
[1, 1, 4, 2, 1, 1, 0, 0]
Why store indices instead of values?
The answer is the gap in days, which is the difference between two indices. If you stored values, you would know a warmer day exists but not how far away it is. Storing indices lets you compute i - prev directly.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class WhyIndices {
public static void main(String[] args) {
int[] temps = {71, 69, 72};
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
int prev = stack.pop();
int gap = i - prev;
System.out.println("Day " + prev + " (" + temps[prev] + ") resolved by day " + i + " (" + temps[i] + "), gap=" + gap);
}
stack.push(i);
}
System.out.println("Unresolved indices: " + stack);
}
}
Day 1 (69) resolved by day 2 (72), gap=1
Day 0 (71) resolved by day 2 (72), gap=2
Unresolved indices: [2]
How does the monotonic decreasing stack work?
The stack holds indices in decreasing temperature order from bottom to top. When a new temperature is higher than the top, the top can be resolved. You keep popping until the stack top is warmer or equal, then push the current index. This maintains the decreasing invariant.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class MonotonicDecreasingDemo {
public static void main(String[] args) {
int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
stack.pop();
}
stack.push(i);
System.out.println("After index " + i + " (" + temps[i] + "): stack indices = " + stack);
}
}
}
After index 0 (73): stack indices = [0]
After index 1 (74): stack indices = [1]
After index 2 (75): stack indices = [2]
After index 3 (71): stack indices = [3, 2]
After index 4 (69): stack indices = [4, 3, 2]
After index 5 (72): stack indices = [5, 2]
After index 6 (76): stack indices = [6]
After index 7 (73): stack indices = [7, 6]
Why use strictly-greater comparison?
The problem asks for a strictly warmer day. Using >= would let equal temperatures resolve each other, which is wrong. If two consecutive days are both 72 degrees, neither is warmer than the other, and using >= would falsely report a wait of 1 day.
package com.bank.core;
public class StrictlyGreater {
public static void main(String[] args) {
int[] temps = {72, 72, 73};
// With > (correct): day 0 waits for day 2 (73), gap=2
// With >= (wrong): day 0 resolved by day 1 (72), gap=1
System.out.println("temps[1]=72 is NOT warmer than temps[0]=72");
System.out.println("Use > not >= to ensure strictly warmer");
System.out.println("Correct answer for day 0: 2 (waits for day 2)");
}
}
temps[1]=72 is NOT warmer than temps[0]=72
Use > not >= to ensure strictly warmer
Correct answer for day 0: 2 (waits for day 2)
What about the unresolved days?
Indices remaining on the stack after the scan have no warmer day ahead. Since the answer array is initialized to 0 by default in Java, these entries are already correct. No separate cleanup loop is needed.
package com.bank.core;
import java.util.Arrays;
public class UnresolvedDays {
public static void main(String[] args) {
int[] answer = new int[5];
System.out.println("Default values: " + Arrays.toString(answer));
// All zeros: perfect for unresolved days
System.out.println("Unresolved days keep their default 0");
}
}
Default values: [0, 0, 0, 0, 0]
Unresolved days keep their default 0
What is the time complexity despite the inner loop?
The inner while loop might look like it makes the algorithm O(n^2), but each index is pushed once and popped at most once. The total number of push and pop operations across all iterations is at most 2n, so the overall time is O(n). This is a standard amortized argument for monotonic stack algorithms.
package com.bank.core;
public class ComplexityProof {
public static void main(String[] args) {
// For n elements:
// Total pushes: exactly n (one per element)
// Total pops: at most n (each element popped at most once)
// Total work: at most 2n = O(n)
System.out.println("Each index: pushed once, popped at most once");
System.out.println("Total operations: at most 2n");
System.out.println("Time complexity: O(n)");
}
}
Each index: pushed once, popped at most once
Total operations: at most 2n
Time complexity: O(n)
How is this applied in banking?
At the National Bank of India, I used this to compute a days-to-recovery metric for a daily market sentiment index. For each day, the dashboard shows how many days passed before sentiment rose above that day's level. One linear pass produces the full array over a long trading history.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class SentimentRecovery {
public static int[] daysToRecovery(double[] scores) {
int[] result = new int[scores.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < scores.length; i++) {
while (!stack.isEmpty() && scores[i] > scores[stack.peek()]) {
int prev = stack.pop();
result[prev] = i - prev;
}
stack.push(i);
}
return result;
}
public static void main(String[] args) {
double[] sentiment = {7.2, 6.8, 6.5, 7.0, 7.5, 7.1};
System.out.println("Sentiment scores: " + Arrays.toString(sentiment));
System.out.println("Days to recovery: " + Arrays.toString(daysToRecovery(sentiment)));
}
}
Sentiment scores: [7.2, 6.8, 6.5, 7.0, 7.5, 7.1]
Days to recovery: [4, 2, 1, 1, 0, 0]
What should a senior engineer know?
This is the Next Greater Element pattern. The same decreasing stack technique finds the next greater element, the next greater element in a circular array (by iterating twice), and the stock span problem (days since the last higher price). Recognizing the monotonic stack pattern across these variants is what interviewers look for at a senior level.
package com.bank.core;
public class MonotonicStackVariants {
public static void main(String[] args) {
System.out.println("Pattern: Monotonic Decreasing Stack");
System.out.println("Variant 1: Next Greater Element -> push values, return value");
System.out.println("Variant 2: Daily Temperatures -> push indices, return distance");
System.out.println("Variant 3: Circular NGE -> iterate array twice (i % n)");
System.out.println("Variant 4: Stock Span -> days since last higher price");
}
}
Pattern: Monotonic Decreasing Stack
Variant 1: Next Greater Element -> push values, return value
Variant 2: Daily Temperatures -> push indices, return distance
Variant 3: Circular NGE -> iterate array twice (i % n)
Variant 4: Stock Span -> days since last higher price
Visual Overview
Monotonic Decreasing Stack Walk
temps = [73, 74, 75, 71, 69, 72, 76, 73]
──────────────────────────────────────────
i=0 73: push 0 stack: [0]
i=1 74>73: pop 0, ans[0]=1 stack: [1]
i=2 75>74: pop 1, ans[1]=1 stack: [2]
i=3 71<75: push 3 stack: [3,2]
i=4 69<71: push 4 stack: [4,3,2]
i=5 72>69: pop 4, ans[4]=1
72>71: pop 3, ans[3]=2 stack: [5,2]
i=6 76>72: pop 5, ans[5]=1
76>75: pop 2, ans[2]=4 stack: [6]
i=7 73<76: push 7 stack: [7,6]
Result: [1, 1, 4, 2, 1, 1, 0, 0]
Key Takeaway
Daily Temperatures is the Next Greater Element pattern adapted to return distances instead of values. I keep a monotonic decreasing stack of indices and scan the array once. When a warmer day arrives, it resolves every pending colder day on the stack, and the answer for each resolved day is the current index minus the popped index.
Storing indices rather than values is essential because the answer is the gap in days, not the warmer temperature itself. The stack maintains a decreasing order from bottom to top, so the top is always the coldest pending day. When a new temperature is strictly greater than the top, I pop and record the distance, then keep popping until the invariant is restored. The strictly-greater comparison prevents equal temperatures from falsely resolving each other.
The time complexity is O(n) despite the inner while loop, because each index is pushed once and popped at most once across the entire scan. Indices remaining on the stack at the end have no warmer day ahead, and the answer array defaults to zero, so no cleanup is needed.
In my project at the National Bank of India, I used this to compute a days-to-recovery metric for a daily market sentiment index. One linear pass over a long trading history produced the full answer array, and the monotonic stack gave the dashboard responsive analytics even on months of daily data.
Remember one sentence: push indices on a decreasing stack, pop and record the gap when a warmer day arrives, and each index is handled at most twice for O(n) total.
---