A monotonic stack keeps unresolved candidates in a useful order. Each item is pushed and removed at most once, giving linear total work.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: A warmer temperature resolves earlier colder days while scanning forward. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Store unresolved candidates
Indices awaiting a warmer day remain on the stack.
Step 2: Resolve when evidence arrives
A warmer current value pops earlier colder candidates and supplies their distance.
Step 3: Count total operations
Each index is pushed once and popped at most once.
Worked scenario
A warmer temperature resolves earlier colder days while scanning forward.
For temperatures [70,72,71,75], day one resolves day zero; day three resolves days two and one. Their distances are [1,2,1,0]. Equal temperatures do not count as warmer under a strict definition, so the comparison must preserve unresolved equal values appropriately.
Common mistake
Using a plain stack without explaining what remains unresolved obscures correctness.
Verify the behavior
Test increasing, decreasing and equal sequences; verify nearest qualifying successors.
Interview exercise
Handle equal values deliberately.
Answer and reasoning
Choose strict or nonstrict comparison from the question’s definition, then test repeated values and absent successors.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.