Monotonic stacks and the next warmer day
Find the first warmer day for every temperature in one pass. A C# stack of unresolved days handles equal readings and explains the linear time bound.
Two days in a row reach 18 degrees. Four days after the first reading the temperature hits 22. Both 18s finally have a warmer day, but one waited four days and the other waited three. If a forward scan overwrites the first pending 18 with the second, it loses the index it needs to record the four-day wait.
The task is to take a sequence of daily readings and, for each index, return how many days pass before the first strictly warmer reading. Write zero for days that never get one. Here's a week's worth of data, numbered from day zero. Notice the 21 near the end. Day four still has no answer, even though day five does.
day 0 1 2 3 4 5 6
reading 18 18 16 17 22 20 21
wait 4 3 1 1 0 1 0A direct solution walks forward from each day until a higher reading appears. Try that on a month of falling temperatures. The first day scans the other 29. The next scans 28. After 435 comparisons you have thirty zeros. Each comparison found a piece of evidence that might have helped another day. A monotonic stack keeps the outstanding questions in an order that lets a new reading answer several of them at once.
Keep a stack of indices. Every entry represents a day whose warmer successor has yet to appear. After processing a reading, the temperatures of those days run from warmest at the bottom to coolest at the top, with ties allowed. Their indices run from oldest to newest. These are two separate properties. One tells you when to stop searching and the other gives you the wait time.
Consider the instant before day four's reading of 22. The stack contains days zero, one and three. Day two, which recorded 16, was removed as soon as day three recorded 17. The chart shows each pending day as index / temperature, oldest on the left. The right edge is the top of the stack.
-
After day 2
- 0 / 18
- 1 / 18
- 2 / 16
The newest day is also the coolest outstanding day.
-
After day 3
- 0 / 18
- 1 / 18
- 3 / 17
Day 3 answers day 2 and joins the stack.
-
After day 4
- 4 / 22
Day 4 has answered all three outstanding days.
Day four pops day three because 22 is warmer than 17. It also pops both days at 18. Their positions give waits of one, three and four respectively. Then day four pushes its own index. Tomorrow might be warmer still, and today's success at resolving old days tells us nothing about its own answer.
Why can the loop stop at the first temperature at least as high as today's? Everything below that entry is equally warm or warmer. Reaching deeper could never reveal another day that today's temperature can resolve. Pushing today at that point preserves the ordering. On a completely empty stack there's nothing to resolve and pushing the new day starts the process again.
Popping a day proves two things. Today's reading is warmer, and every intervening reading had its chance to pop that day and left it waiting. That second fact is what makes today's match the first.
This method reads the input once from left to right. The result array starts with zeros. An entry is written exactly once if a warmer reading exists and keeps its initial zero otherwise. Empty input and a single reading fall out of the same loop.
static int[] DaysUntilWarmer(int[] readings)
{
var waits = new int[readings.Length];
var waiting = new Stack<int>();
for (int today = 0; today < readings.Length; today++)
{
while (waiting.TryPeek(out int earlier) && readings[earlier] < readings[today])
{
waiting.Pop();
waits[earlier] = today - earlier;
}
waiting.Push(today);
}
return waits;
}It is tempting to make the comparison inclusive because sorting examples often use "less than or equal" to handle ties. Here the English word warmer decides the test. With two identical readings, popping on equality writes a wait of one for the first day even though no warmer day exists. Dropping the older duplicate without recording a wait is wrong too. A later warm day may need to answer both. Extending a fixture from [18, 18] to [18, 18, 19] distinguishes those bugs. The correct outputs are [0, 0] and [2, 1, 0].
Another common mix-up is to find a warmer day somewhere later and forget the word first. In [15, 16, 25], the wait from day zero is one. A suffix maximum can tell you that 25 occurs after day zero, and even that some warmer day exists. Choosing the position of that maximum returns two. Processing the candidates in chronological order gives the stack exactly the ordering the question demands.
The while loop is inside the for loop. On the final day of a long cool spell it really can execute almost once per previous day. That makes the cost of processing one reading spiky. It also makes a worst-case multiplication of the two loop bounds misleading. To fund each successful pass through the inner loop, produce the index that it removed. That index entered once, and can never enter again.
Across n readings there are exactly n pushes and at most n - 1 pops for nonempty input. A check that stops the inner loop occurs at most once per reading. Total time is therefore O(n), including the array initialization. A week of steadily rising temperatures keeps at most one pending entry after each day. A week of falling or equal readings keeps all seven. Worst-case additional space is O(n), on top of the O(n) output. The bound needs no assumption about a particular range of temperatures, so the method works on negative readings too. Counting how much work a whole run can do is a useful companion to measuring the cost at larger input sizes.
For a short sequence the obvious scan is cheap enough to use as an independent reference. Generate all sequences of length five from the temperatures 16, 17 and 18. There are only 243. Compare every output entry from the stack with the first warmer reading found by walking forward. The small alphabet deliberately puts equal values into many positions. In a suite of five distinct readings chosen at random, a mistaken equality rule would never be exercised. Using a simple implementation as a reference is one way to get more from property-based tests.
For a load case, reverse the distribution. Give the implementation a descending series of 20,000 distinct readings. A fresh search from each index does exactly 20,000 × 19,999 / 2 temperature comparisons, or 199,990,000. The stack finishes with 20,000 entries, and after the first day each new reading compares against just the top. The price of holding the indices is visible precisely where the repeated searches cost the most. Time and allocated memory answer different questions about that trade. Katabench's performance guide explains how those measurements appear for an individual test.
The Daily Temperatures kata in C# coding challenges uses this first-warmer-day contract. Before running a large input, try a plateau followed by one warmer day and write down the waits by hand. Every entry on the plateau has the same temperature. The descending sequence of waits is how you can tell your stack remembered each day.
Practice what you just read
- Open in the editor: Daily Temperatures
Algorithm Medium Free, no account needed
Daily Temperatures
For each day, how long until a warmer one?
More like this: C# coding challenges →