Skip to content

Volume ITechnology

4.8.0 — Stack & Monotonic Stack: The Pattern ​

Recognition cue, part one — the plain stack. The problem involves nesting, undoing, or matching pairs. Brackets, expression evaluation, backtracking state.

Recognition cue, part two — the monotonic stack. The problem asks for the nearest greater or smaller element on one side, or for a span, or for a distance to some future event. The brute force is a nested loop that scans forwards or backwards from each position.

The one sentence ​

A monotonic stack computes on eviction, not on insertion.

Everything difficult in this group dissolves once you hold that. When an item is popped, both of its boundaries are known: the item that triggered the pop is the nearest smaller-or-larger element on one side, and whatever is left on top of the stack is the nearest on the other side. Neither is known before the pop, which is why trying to compute at push time feels impossible.

The templates ​

python
# 1. Plain stack — nesting and matching
stack = []  # (1)
for c in s:
    if is_opener(c): stack.append(c)  # (2)
    else:
        if not stack or stack.pop() != partner(c): return False  # (3)
return not stack  # (4)

# 2. Monotonic stack — next greater to the right
stack = []                      # (5) indices, values DECREASING
for i, v in enumerate(nums):
    while stack and nums[stack[-1]] < v:      # (6) ← flip this comparison
        j = stack.pop()  # (7)
        answer[j] = i - j                     # (8) ← compute HERE, at the pop
    stack.append(i)  # (9)

The templates, line by line.

(1) Template 1 is a plain stack of opened things. (2) Push every opener. (3) A closer must match the most recent unclosed opener. If the stack is empty or the top does not match, the input is broken. (4) At the end, nothing may be left open.

(5) Template 2 keeps a stack of positions still waiting for an answer, with their values going down from bottom to top. (6) While the newest waiting value is smaller than the new value, (7) the new value is the answer it was waiting for. Pop it, (8) and record the answer at the moment of the pop. That is when it becomes known. (9) The new position now waits for its own answer. Flip < to > to find the next smaller value instead.

The two things that change between problems are the comparison and the direction of travel:

you wantcomparisondirection
next greater to the righttop < currentleft to right
next smaller to the righttop > currentleft to right
next greater to the lefttop < currentright to left
next smaller to the lefttop > currentright to left

Derive this once by asking what makes an item on the stack useless, rather than memorising it.

The seven problems ​

#ProblemThe one insight
4.8.1Valid Parentheses ★Nesting means the most recent opener must match first
4.8.2Min Stack ★Remember the minimum per level, not globally
4.8.3Evaluate RPNAn operator consumes the two most recent results
4.8.4Generate Parentheses ★Backtracking: never build an invalid prefix
4.8.5Daily TemperaturesKeep only the days still waiting, in decreasing order
4.8.6Car FleetSort by position, then count increases in arrival time
4.8.7Largest Rectangle in HistogramEvery rectangle has a shortest bar; ask how far it reaches

★ marks the Blind 75 subset.

The traps on this pattern ​

Trying to compute at push time. The right boundary is not known yet. Compute at the pop.

Storing values instead of indices. If the answer is a distance or a width, you need positions.

Forgetting the leftover stack. Items still on the stack at the end never found their match. Either initialise the answer array to the right default, or push a sentinel value that flushes everything through the normal path — a 0 for histograms, an infinity for minimum problems.

< versus <=. Decide whether equal values should evict each other. For Daily Temperatures, "warmer" is strict, so use <. For Min Stack, duplicate minima each need their own entry, so use <=.

Integer division. Python's // floors, so -13 // 5 is -3 when RPN needs -2. Use int(a / b). In Car Fleet, integer division destroys fractional arrival times entirely — use /.

list.pop(0) as a queue. O(n) in Python. Use collections.deque.

What the interviewer will push on ​

"Why is a monotonic stack O(n) when there is a loop inside a loop?" Each index is pushed exactly once and popped at most once, so the total work is 2n. This is asked on every problem in the group.

"Derive the width formula in Largest Rectangle." Right boundary is the bar that triggered the pop, left boundary is the new stack top, and the rectangle spans strictly between them: right - left - 1.

"Why <= in Min Stack?" Duplicate minima. Give the [2, 2] example.

"What is the sentinel for?" To force the remaining stack to be resolved through the same code path instead of a second loop.

"Change this to find the next smaller element instead." Flip the comparison. Answering instantly shows you understand the structure rather than the problem.

One thing to volunteer: state the eviction rule as a sentence before writing code. "An item is useless once a later item makes it unable to ever be the answer, so it leaves the stack — and that is the moment I can compute its result."

Recall

  • Plain stack = nesting, matching, undo. Monotonic stack = nearest greater or smaller element, spans, distances.
  • Compute on eviction, not on insertion. At the pop, the triggering item is one boundary and the new stack top is the other.
  • Store indices when the answer is a distance or width.
  • Two knobs change between problems: the comparison and the direction of travel.
  • A sentinel at the end (0 for histograms) flushes the stack through the normal path and removes the cleanup loop.
  • O(n) because each index is pushed once and popped once — 2n operations in total.
  • Min Stack needs <= so duplicate minima each get an entry. RPN needs int(a/b), not //. Car Fleet needs float division.

Next: 4.8.1 Valid Parentheses — the plain stack at its simplest, and the problem that shows why counting is not enough.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet