Understanding the problem

A trader wants to know, for each day's closing price, how many days pass before the price is higher. The natural first answer walks forward from every day:

for i in range(n):
    for j in range(i + 1, n):
        if price[j] > price[i]:
            wait[i] = j - i
            break

On a rising market this is fast, because every inner loop stops after one step. On a falling market it is a disaster: no day ever finds a higher price, and every inner loop runs to the end of the array.

On a steadily falling series the inner loop runs n − 1, then n − 2, and so on: about n²/2 comparisons in total.

Worse, the work is wasted in a specific way. When day 5 scans forward past days 6, 7 and 8, it learns that each of them is lower than day 5. Then day 6 scans the same stretch again and learns almost the same thing. The brute force keeps no memory of what it has already seen.

Instead of each day going to look for its answer, let the answers come to the days. Walk through the prices once and keep a list of the days that have not yet seen a higher price. When a new price arrives, it is the answer for every waiting day it beats.

Which waiting days does it beat? Always the most recent ones. A day can only still be waiting if nothing after it was higher, so the waiting prices fall from oldest to newest. The new price removes waiting days from the newest end until it meets one it does not beat, then joins the list itself. Adding and removing at the same end is a stack.

There is a while loop inside the for loop, so it looks quadratic. Count differently: every day is added to the stack once and removed at most once. However the removals are spread across the iterations, their total over the whole run is at most n. That style of argument, charging the work to the elements rather than to the loop iterations, is called amortised analysis, and interviewers expect you to give it whenever you write a loop like this.

The stack holds questions that are still open. Each new element closes some of them and opens one of its own. When a problem asks about the nearest larger or smaller element, or the matching partner of something seen earlier, that is the picture to reach for.