Monotonic stacks: next greater and spans

A monotonic stack is a stack whose items stay in sorted order from bottom to top. It answers “nearest” questions for every item of a list in one pass: the next item that is greater, the next that is smaller, or the previous one of either kind. Asked one at a time, each of these questions needs a scan, so a list of n items costs O(n²); kept on a monotonic stack, all n answers cost O(n) together. This lesson starts from an original problem about a weather log, shows the brute force and where it breaks, and then uses one loop for next greater elements, the spans of a price series and the largest rectangle under a bar chart.

The problem: days until a hotter day

A city’s weather office publishes the highest temperature of each day of a log. For every day, report how many days you must wait for a strictly hotter day, or 0 if no hotter day follows within the log.

• Input: n whole numbers, temps[0] to temps[n - 1], with 1 ≤ n ≤ 2 × 10⁵ and −50 ≤ temps[i] ≤ 60.
• Output: n numbers. answer[i] is the smallest d > 0 with temps[i + d] > temps[i], or 0 if there is none.
• Time limit: about one second.

Three examples:

• [31, 29, 33, 33, 30, 35] gives [2, 1, 3, 2, 1, 0]. Day 2, at 33°, waits three days: day 3 is just as hot, which does not count, and day 5, at 35°, is the first hotter one.
• [40, 38, 36, 34] gives [0, 0, 0, 0]: the log only cools.
• [20, 21, 22] gives [1, 1, 0].

The brute force: scan forward from every day

For each day, look at the days after it, one by one, until one is hotter.

def days_to_wait_brute(temps):
    """For each day, scan forward to the first strictly hotter day. Returns the answers and the comparisons made."""
    n, comparisons = len(temps), 0
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if temps[j] > temps[i]:
                answer[i] = j - i
                break
    return answer, comparisons


print(days_to_wait_brute([31, 29, 33, 33, 30, 35])[0])
print(days_to_wait_brute([40, 38, 36, 34])[0])
print(days_to_wait_brute([20, 21, 22])[0])
print()
print(f"{'n':>7}  comparisons on a strictly falling log   n(n-1)/2")
for n in [1_000, 2_000, 4_000]:
    _, comparisons = days_to_wait_brute(list(range(n, 0, -1)))
    print(f"{n:>7,}  {comparisons:>38,}  {n * (n - 1) // 2:>10,}")

[2, 1, 3, 2, 1, 0]
[0, 0, 0, 0]
[1, 1, 0]

      n  comparisons on a strictly falling log   n(n-1)/2
  1,000                                 499,500     499,500
  2,000                               1,999,000   1,999,000
  4,000                               7,998,000   7,998,000

It gives the right answers, and it is slow exactly when the log keeps cooling: then no scan finds a hotter day, every scan runs to the end of the log, and the comparisons add up to n(n − 1)/2, as the counts for falling logs show. At n = 2 × 10⁵ that is about 2 × 10¹⁰ comparisons. Python manages a few tens of millions of such steps a second, so the brute force would need tens of minutes, and even compiled code would need many seconds: far over the limit.

What to notice

Look at the days that are still waiting for an answer after any day of the log. Read from the oldest to the newest, their temperatures never rise: if a newer waiting day were hotter than an older one, the older one would already have its answer. So a new day only has to compare itself with the newest waiting days, and every waiting day it is hotter than gets its answer at that moment.

The stack of waiting days, step by step Pro: opens with a Pro, Premium or Ultimate pass