Stack and monotonic stack

How long until a larger amount arrives

A fraud model needs one more input. For every transaction at a merchant, taken in time order, it wants to know how many transactions pass before a larger amount arrives. People testing stolen cards often send a run of small amounts before a large one, and this number picks out that run.

The direct way is to walk forward from each transaction until a larger amount turns up. Most merchants finish in seconds. Then the job reaches a merchant whose amounts fall steadily all day. It has 200,000 transactions, and none of them is ever followed by a larger one, so each walk goes to the end of the day. Work out the cost: 200,000 × 200,000 ÷ 2 is 20 billion steps for that one merchant, and there are 30,000 merchants.

Stop the scan at one moment and look at the transactions that are still waiting for a larger amount, oldest first: ₹1,500, ₹700, ₹400. The next transaction is ₹900.

Pause and predict The waiting transactions are ₹1,500, ₹700 and ₹400, oldest first, and the next transaction is ₹900. For which of the waiting transactions is the ₹900 the first larger amount?

The most recent unfinished thing

Some inputs give you elements that cannot be finished when they arrive. An opening bracket waits for its closing bracket. A number in 3 5 + waits for its operator. A day waits for a warmer day.

When the element that finishes next is always the one that started most recently, the memory you need is a stack. Push each element that cannot be finished yet. When something arrives that finishes the element on top, pop it and finish it.

Pause and predict A bracket string so far has opened {, then [, then (, and none of them is closed yet. The next character is ]. What does that mean?

Min Stack, reverse Polish notation and Decode String follow the same rule, each with a different meaning for finishing an element. In Min Stack, a pop returns the stack to an earlier state, so each entry can store the minimum of the stack as it was when that entry was pushed.

When an element's answer is the next element that beats it

Daily Temperatures asks, for every day, how many days pass until a warmer day. Scanning forward from every day is O(n²).

Which days are still waiting when the scan reaches day i? The ones that have not yet been followed by a warmer day. Keep them on a stack. Their temperatures never rise from bottom to top: if a waiting day were warmer than an earlier waiting day, it would have been the earlier day's answer, and the earlier day would have left the stack.

So when today is warmer than the day on top of the stack, today is that day's answer. Pop it and write its answer down. Keep popping while today is warmer than the new top. Then push today, because it is waiting for a warmer day too.

A stack whose values only fall (or only rise) from bottom to top is called a monotonic stack. The code has a while loop inside a for loop, which looks quadratic.

Pause and predict Over the whole scan of n days, how many pops can the inner while loop do in total?

Push indices rather than values, for three reasons. The answer is usually a distance (i - j), which needs positions. Equal values at different days must stay separate. And the value is one array lookup away from its index, while a value cannot give you back its index.

Two more shapes of the same idea

The maximum of every window. In Unit 3 a window keeps a running sum, and when an element leaves you subtract it. You cannot do that with a maximum. Instead, keep the window's indices on a monotonic stack and give it a second exit: the oldest index is removed from the bottom when it falls out of the window. A structure you can add to and remove from at both ends is called a deque.

When a newer value is at least as big as an older one, the older one is popped for good, because the newer value is just as large and stays in the window longer. The values that remain fall from front to back, so the front of the deque holds the maximum.

Largest Rectangle in Histogram. For each bar, ask how far a rectangle exactly as tall as that bar can extend. It extends until the first shorter bar on each side. Keep a stack whose heights rise from bottom to top. When a bar is popped, the bar that popped it is the first shorter bar on its right, and the new top of the stack is the first shorter bar on its left.

How to recognise it

What these problems have in common: an element's answer depends on something that comes later in the input, and the most recent unfinished element is settled first.

The part you have to get right is the comparison in the pop loop. Work it out from the question: which waiting elements does the new element answer? Pop exactly those.

Pause and predict You want the next strictly greater value. Day 0 is 70 and is waiting on the stack, and day 1 is also 70. Should day 1 pop day 0?

If you scan from right to left instead, "next" and "previous" swap roles, and the same argument works in mirror image.

The ones that only look like it

• If the question is about a contiguous range and its sum, a count, or a set of letters, the window's own contents are all you need to track. That is sliding window. Only the window's maximum or minimum needs the deque.
• If you need the k largest values or the median of a stream, elements are settled in no particular order, so a stack does not fit. That is heaps.
• If the input is a row of heights and each decision is about the two outermost walls, as in Container With Most Water, that is two pointers.

Where it bites

Pause and predict In the histogram, bar j is popped by bar i, and after the pop the top of the stack is bar t. How wide is the rectangle that has bar j's height?

• Pushing values instead of indices. You lose the distance i - j, equal values can no longer be told apart, and a deque can no longer tell when its front has left the window.
• Choosing < or <= out of habit. Decide from the question whether an equal value answers the waiting element. "Warmer" means strictly greater, so equal days stay on the stack.
• The wrong width in the histogram. After popping bar j, the left limit is the new top, so the width is i - newTop - 1, or i when the stack is empty.
• Forgetting the elements still waiting. When the scan ends, the stack may not be empty. Give those elements the default answer, or add an extra bar of height 0 at the end so that it pops everything.
• Removing the deque's front one step late. The window is [i - k + 1, i], so remove the front when its index is <= i - k.