Warmer Day Countdown

Problem Statement

You're given a list of daily temperatures, one integer per day, in order. For each day, figure out how many days you'd have to wait until a day with a strictly warmer temperature comes along, and print that count. If no day after it is ever warmer, print 0 for that day instead.

Input Format

The input is exactly one line: the temperatures, as space-separated integers, one per day in chronological order.

Output Format

Print one line containing, for each day in order, the number of days until a strictly warmer day (or 0 if none exists), separated by single spaces.

Example Walkthrough

Take the second sample, 30 40 50. Day 0 has temperature 30. Looking forward, day 1 (40) is the very next day and it's already warmer than 30, so day 0's answer is 1 - 0 = 1 day. Day 1 has temperature 40; day 2 (50) is warmer, one day later, so day 1's answer is also 1. Day 2 has temperature 50, the highest of the three — there's no day after it at all, so it can never find a warmer one, and its answer is 0. Putting these together gives 1 1 0.

Approach

The direct way to solve this is, for each day, to scan forward through every later day until a warmer one turns up. That works, but in the worst case — say, temperatures that only ever decrease — every day scans all the way to the end of the list without finding anything, giving O(n²) time overall.

A stack lets you find each day's answer in a single left-to-right pass. The idea is to maintain a stack of day-indices whose warmer day hasn't been found yet — think of it as a "waiting list," and because you only ever push a day after checking it isn't immediately resolved by something already on the stack, the temperatures corresponding to the indices on the stack are always in decreasing order from bottom to top. As you scan to a new day, compare today's temperature to the temperature at the index on top of the stack. If today is warmer, that day was waiting exactly for something like today: pop it off the stack and record its answer as today's index minus its own index. Keep popping and recording as long as the new top of the stack is also cooler than today — a single warm day can resolve several waiting days at once, if they were all cooler than it. Once the stack's top is no longer cooler than today (or the stack is empty), push today's own index onto the stack, since it's now the one waiting for its own warmer day.

By the time the scan reaches the end of the list, any day-index still left on the stack never found a warmer day at all, so those days keep their answer at 0 (the value they were initialized with). Every day-index is pushed onto the stack exactly once over the whole scan, and popped at most once, so the total work across all the pushes and pops together is O(n), even though any single day's temperature might resolve many earlier waiting days in one step.

Common Mistakes

• Comparing with <= instead of < when popping from the stack. The problem asks for a strictly warmer day. If a day with the exact same temperature as one still on the stack incorrectly counts as "warmer," a day waiting for genuine warming gets resolved too early with a wrong answer.
• Recording the temperature difference instead of the day difference. The expected output is a count of days to wait, not how many degrees warmer the later day is — mixing these up produces numbers that might look plausible but don't match what the problem is actually asking for.
• Never popping more than one day per step. A single very warm day can resolve several cooler days that were all waiting on the stack at once (for example, a sharp temperature spike after several cooler days). If the popping step only checks the top of the stack once instead of repeating the check-and-pop in a loop, only the most recently pushed waiting day gets resolved, and the rest are left incorrectly waiting for a later, possibly non-existent, warmer day.