[00:01] daily temperatures and asks, "For each day, count how many days until the next Now, your instinct might be to pick each day and then just scan forward until a warmer day appears. That does work, but then they say that the input is maybe a
[00:14] million days, and that O of N squared solution is going to take a trillion See, you can actually do this in a single pass. All you need is a stack of indices for the days still waiting on a warmer
[00:26] So, when a warmer day does show up, every colder day on the stack just found its answer. You now know exactly how long each one waited. So, you pop them off and you record the gap for each. Let's quickly trace it on an example.
[00:39] The first three days only get cooler, so each one pushes its index and waits. The each one pushes its index and waits. The stack now holds 0, 1, and 2, decreasing from bottom to top. 72 is warmer than the 69 on top. So, you
[00:52] 1. It's still warmer than the 71 now on It's still warmer than the 71 now on top, so pop index 1 and record 3 - 1, which is 2. One warmer day just cleared two waiting days.
[01:05] Every index gets pushed once and popped once, so that previous O of N squared scan now collapses into one linear sweep. element to the right, reach for a monotonic stack.
[01:18] Follow us for more coding interview breakdowns at hellointerview.com.