MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 8 – Stacks and monotonic stacks

Next greater element with a monotonic stack

For every day, how long until a warmer one? Find the next greater element of each position in one pass with a monotonic stack, from brute force to proof.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free: The problem: days until a warmer day. With a pass: the other 10 sections and 3 interview answers, about 16 minutes.

What you will learn

  • Find the next greater or next smaller element of every position in O(n) time
  • Prove that the stack gives every position its right answer, and count its work
  • Choose the strict or the non-strict comparison that matches the tie rule of a problem
  • Extend the method to previous-greater, next-smaller and circular versions
  • Test a monotonic stack against a brute force on random inputs with many ties

Before you start

What you’ll learn · Before you start

What you will learn

  • Find the next greater or next smaller element of every position in O(n) time
  • Prove that the stack gives every position its right answer, and count its work
  • Choose the strict or the non-strict comparison that matches the tie rule of a problem
  • Extend the method to previous-greater, next-smaller and circular versions
  • Test a monotonic stack against a brute force on random inputs with many ties

Before you start

On this page

The next greater element: For a position in a list, the first value after it that is strictly larger. In 31, 29, 33 it is 33 for both 31 and 29, and the last value has none. of a position in a list is the first value after it that is strictly larger: in 31, 29, 33, it is 33 for both 31 and 29. Asked for every position at once, the question has a slow answer, scanning forward from each position, and a fast one: a monotonic stack: A stack whose values stay in order from bottom to top, because each new item first pops every item it settles. It finds the nearest earlier or later larger, or smaller, item for every item in one pass. More in “Stack patterns: nesting and undo”, which holds the positions still waiting for their answer, with values that never rise from the bottom to the top. Each new value answers the waiting positions it beats, newest first, and then waits itself, so a list of n values takes O(n) time where the scans take O(n²). The problem is widely known as daily temperatures: how many days until a warmer day? The same loop answers the previous greater, next smaller and circular versions, each with one change.

The problem: days until a warmer day

The problem

A weather station records the highest temperature of each day, in whole degrees Celsius: temps[0..n − 1]. For every day i, report wait[i], the number of days from day i to the first later day that is strictly warmer, or 0 when no later day is warmer. Limits: 1 ≤ n ≤ 100,000 and −50 ≤ temps[i] ≤ 60.

Three examples, which every program in this lesson runs:

  1. [31, 29, 33, 30, 30, 35, 32] gives [2, 1, 3, 2, 1, 0, 0]. Day 3 waits past day 4, which is just as warm, not warmer.
  2. [40, 38, 36] gives [0, 0, 0]: the days only cool.
  3. [27, 27, 28] gives [2, 1, 0].
Bars for the seven temperatures, with arrows from each day to its first warmer day; the waits are 2, 1, 3, 2, 1, 0 and 0.Highest temperature each day (°C)31293330303532daywait02112332415060

Each day points to its first warmer day; the dashed bars have none

Text description of the diagram

The chart shows the seven days of the first example as bars, from day 0 to day 6, with their highest temperatures in °C: 31, 29, 33, 30, 30, 35 and 32. Under each bar are the day's number and its answer, the wait. Arrows below the chart join each day to the first later day that is strictly warmer.

  1. Day 0 (31 °C) and day 1 (29 °C) both point to day 2 (33 °C): they wait 2 days and 1 day.
  2. Day 2 (33 °C), day 3 (30 °C) and day 4 (30 °C) all point to day 5 (35 °C): they wait 3, 2 and 1 days. Day 4 has the same temperature as day 3, which is not warmer, so day 3 waits past it.
  3. Day 5 (35 °C) and day 6 (32 °C) have no warmer day after them. Their bars are dashed and their answer is 0.

The arrows never cross: when one arrow lies over another, it covers it entirely. Several days can wait for the same warm day, and a day that is still waiting is never warmer than an earlier day that is still waiting.

The brute force: scan forward from every day

From each day, read the following days in order and stop at the first warmer one. It is plainly correct, so it is the judge for faster code, but a day with no warmer day after it reads every later day. The run counts comparisons on a log that cools steadily, where no day is warmer than an earlier one, and on random readings between 20 and 45 °C.

Scan forward from every day, and count the comparisons Python · brute/warmer_brute.py 
"""Days until a warmer day, the brute force: from every day, scan forward until a strictly warmer day."""

import random


def wait_for_warmer_brute(temps):
    """wait[i]: how many days after day i the first strictly warmer day comes (0 if none), and the comparisons made."""
    n = len(temps)
    wait = [0] * n
    comparisons = 0
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if temps[j] > temps[i]:
                wait[i] = j - i
                break
    return wait, comparisons


print(wait_for_warmer_brute([31, 29, 33, 30, 30, 35, 32])[0])
print(wait_for_warmer_brute([40, 38, 36])[0])
print(wait_for_warmer_brute([27, 27, 28])[0])

# A log that never warms up: it cools from 60 to -50 degrees and stays level in between.
for n in (1_000, 2_000):
    cooling = [60 - 110 * i // n for i in range(n)]
    print(f"cooling log of {n:,} days: {wait_for_warmer_brute(cooling)[1]:,} comparisons")

rng = random.Random(42)
for n in (5_000, 10_000):
    readings = [rng.randint(20, 45) for _ in range(n)]
    print(f"random log of {n:,} days (20 to 45 degrees): {wait_for_warmer_brute(readings)[1]:,} comparisons")

Output

[2, 1, 3, 2, 1, 0, 0]
[0, 0, 0]
[2, 1, 0]
cooling log of 1,000 days: 499,500 comparisons
cooling log of 2,000 days: 1,999,000 comparisons
random log of 5,000 days (20 to 45 degrees): 490,523 comparisons
random log of 10,000 days (20 to 45 degrees): 1,971,665 comparisons

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 warmer_brute.py

Doubling the log quadruples the work in both cases. A cooling log costs exactly n(n − 1)/2 comparisons, 4,999,950,000 at the limit of 100,000 days: close to a minute of C++ even at 10⁸ simple steps a second, the planning figure of the lesson on constraints, where a second is allowed. Random readings are hardly kinder: the hottest days never meet a warmer day, so each reads to the end, and the same fourfold rule leads to about 2 × 10⁸ comparisons, two seconds at that rate.

Checkpoint

Check: What scanning forward from every day costs

  1. One question A log of 3,000 days cools steadily, so no day is warmer than any earlier day. How many comparisons does the brute force make?

    Type a number.

    A hint

    Day i reads every later day, because none of them is warmer.

    Show the answer

    Answer: 4498500 comparisons

    Day 0 reads 2,999 days, day 1 reads 2,998, and so on down to the last day, which reads none: n(n − 1)/2 = 3,000 × 2,999 / 2 = 4,498,500. The run's 1,000 days gave 499,500 by the same formula, about a ninth as many.

What to notice

The scans repeat one another. Day 2 answers days 0 and 1 at once, yet the brute force found that out twice. Day 5 likewise answers days 2, 3 and 4, which the brute force found in three more scans. Now look at the days whose answer is still open: from the oldest to the newest they never get warmer, because a warmer newer day would already have answered the older one. So a new reading can only answer a run of the newest open days, which is the stack cue from the overview of this module.

Checkpoint

Check: The days still waiting for a warmer day

  1. One question Days 0 to 4 of the first example have been read: 31, 29, 33, 30 and 30 °C. Which days are still open, with no warmer day so far?

    Choose one answer.

    Show the answer

    Answer: Days 2, 3 and 4

    Day 2 answered days 0 and 1. Days 2, 3 and 4 are still open, and their temperatures, 33, 30 and 30 °C, never get warmer from the oldest to the newest: a warmer newer day would already have answered the older one.

The questions below practise both ideas.

Practice that adapts to you

Practise this lesson

6 questions about 8 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 6 Which days make the brute force read every later day of the log?

    Choose one answer.

    Show the answer

    Answer: The days with no warmer day after them

    From each day the brute force reads forward until a strictly warmer day. Days with no warmer day after them read every later day, which is why a cooling log costs n(n − 1)/2 comparisons.

  2. Question 2 of 6 The recorded run needed 1,971,665 comparisons for 10,000 random days. By the same rule, about how many does a random log of 100,000 days need?

    Choose one answer.

    Show the answer

    Answer: About 2 × 10⁸

    The work grows with n²: 10 times the days, 100 times the comparisons, so about 1.97 × 10⁸, about two seconds of C++ at 10⁸ simple steps a second, where a second is allowed.

  3. Question 3 of 6 Most random days meet a warmer day soon. Why is the brute force still quadratic on random readings?

    Choose one answer.

    Show the answer

    Answer: The hottest readings never meet a warmer day, so each of them reads to the end of the log

    About one day in 26 reads 45 °C, the maximum, and none of them meets a warmer day: each scans to the end. Those days alone make the total grow with n².

  4. Question 4 of 6 Why do the open days, read from the oldest to the newest, never get warmer?

    Choose one answer.

    Show the answer

    Answer: A newer open day that was warmer than an older one would already have answered it

    If an open day j were followed by a warmer open day k, then day k, or an earlier warmer day, would be j's answer, and j would not be open. So the open days never get warmer from the oldest to the newest.

  5. Question 5 of 6 For which of these logs of n days are all n days still open when the log ends?

    Choose every answer that is right.

    Show the answer

    Answer:

    • A log that cools steadily, never warming from one day to the next
    • A log in which every day has the same temperature

    A day is answered only by a strictly warmer later day. In a log that never warms, equal days included, no day is ever answered. A warming log answers every day at once, and the zigzag log answers each 25 °C day the next day.

  6. Question 6 of 6 A new reading arrives. Which open days can it answer?

    Choose one answer.

    Show the answer

    Answer: A run of the newest open days, each cooler than the new reading

    Because the open days never get warmer from the oldest to the newest, the days a new reading beats form a run at the newest end. That is the stack cue: work only at the top.

A stack of open days settles every day in one pass Pro

In this part:

  • A dry run on the first example
  • The invariant, and the proof that every answer is right
  • Counting the work: at most 2n pushes and pops, measured
  • The code in 14 languages, and the empty-stack check each needs
  • Ties, slips and the stress test that finds them
    • Strict or not: the comparison is the tie rule
    • Edge cases to test before you submit
  • The same loop answers previous, smaller and circular versions
  • Practise: the next busier server in a ring
    • Find the next busier server in a round-robin ring
  • Follow-up questions, answered
  • Interview questions
    • What does a monotonic stack keep, and why are the values on it in order?
    • An interviewer points at the while loop inside your for loop and says your next-greater solution is O(n²). Show that it is O(n), and say which input makes the stack largest.
    • Your next-greater code passes the sample tests, but a hidden test fails, and the inputs can repeat values. What do you check first, and which three small tests do you add?
    • A sensor sends one reading a minute for a year, and each reading's wait for a higher one must be reported as soon as it is known. How much memory can the waiting readings take, and how would you bound it?
  • Key takeaways

2 diagrams · 4 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 42 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

next greater element
For a position in a list, the first value after it that is strictly larger. In 31, 29, 33 it is 33 for both 31 and 29, and the last value has none.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install.

Report a problem with this lesson