What is a monotonic stack and when do you use it? | Interview Question

Q: What is a monotonic stack and when do you use it?

**Target Audience:** Beginners preparing for coding interviews; you should know what a stack is. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the **Verified** section quotes the real output. ## 1. Why This Even Matters — A Story First Imagine people standing in a line at a viewpoint, all facing right, towards a mountain. Each person wants to know: *who is the first person to my right who is taller than me?* That is the person who blocks my view. Checking every person against everyone to their right takes ages. Here is a faster way. Walk along the line from left to right, keeping a little group of "people still waiting for an answer". Whenever a new person arrives, everyone in the waiting group who is shorter than the newcomer has found their answer: it is the

The problem

Question presented to candidate: "What is a monotonic stack? Explain it, tell me which kinds of problems it solves, and code a Python example such as next greater element, explaining why it is O(n)."

What a strong answer should cover:

A stack kept sorted (increasing or decreasing) by popping before each push; popped elements get their answer from the new element.
The four variants: next or previous, greater or smaller, and how strict versus non-strict comparison handles duplicates.
O(n) time because each index is pushed once and popped at most once, despite the nested loop.
Recognising the pattern: nearest greater or smaller, spans, histogram rectangle, trapping rain water; and when a heap or monotonic deque fits better.
Python specifics: a list of indices with append/pop/[-1], [-1] * n for defaults, enumerate, and while stack and ... relying on short-circuit evaluation.

Code / implementation expected: Yes — a short Python next-greater (or stock span) function using a list as the stack.

stack
monotonic

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know what a stack is. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the Verified section quotes the real output.

1. Why This Even Matters — A Story First

Imagine people standing in a line at a viewpoint, all facing right, towards a mountain. Each person wants to know: who is the first person to my right who is taller than me? That is the person who blocks my view.

Checking every person against everyone to their right takes ages. Here is a faster way. Walk along the line from left to right, keeping a little group of "people still waiting for an answer". Whenever a new person arriv

The solution is hidden so you can try first

9 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonAll four variants on one array

Practice

PythonOnline stock span, counting pushes and pops

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.