What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Stack Foundation: Monotonic and Nesting Stacks • Invariant Proof & Speed-Run

Theory Context•Stack

Conceptual Foundation & Intuitive Analogy

Checking future days for each day's "next warmer day" is O(N²). A monotonic decreasing stack resolves all days in a single linear pass by storing unresolved cooler days until a warmer day arrives.

🧭 Conceptual Foundation & Pattern Intuition

For each day in an array of temperatures, we want to know how many days we must wait until a warmer temperature arrives. A brute-force nested loop compares each day $i$ with all future days $j > i$ , costing $O(N^2)$ time and timing out on $N = 10^5$ . The key observation is that colder days cannot resolve each other:

If Day 2 is colder than Day 1, Day 2 cannot be Day 1's answer, but both Day 1 and Day 2 are now waiting for some future warmer day.
A Monotonic Decreasing Stack stores the indices of days that are still waiting for a warmer temperature.
When we iterate to day $i$ $i$ with temperature $T[i]$ $T [i]$ :
- While the stack is non-empty and $T[i] > T[\text{stack}[-1]]$ : day $i$ is the very first warmer day for the day at the top of the stack! We pop prev_idx = stack.pop() and record the waiting duration: answer[prev_idx] = i - prev_idx.
- We push index $i$ onto the stack.
Any day remaining on the stack when the loop terminates never found a warmer day, correctly remaining 0.

🎫 The Analogy: The Waiting Room for Outdoor Cafe Seating

Imagine people waiting for outdoor patio seating at a mountain cafe. Customer A arrives on a 60° day and says "Call me when it gets warmer." Customer B arrives on a 55° day and sits next to Customer A. Customer C arrives on a 50° day. The waiting room is ordered from warmest to coldest. Suddenly, an 65° sunny afternoon arrives! The hostess walks into the waiting room: 65° is warmer than Customer C (50°), so C is seated. It's warmer than Customer B (55°), so B is seated. It's warmer than Customer A (60°), so A is seated! One single warm day clears the entire waiting room in one sweep.

🔑 Why It Works

Even though there is a while loop inside a for loop, every index is pushed onto the stack exactly once and popped at most once. Total operations across the entire array are strictly bounded by $2N$ , guaranteeing amortized $O(N)$ linear time.

Visual Blueprint & State Transition Model

Stack Mental Model Diagram — Figure 1 • Stack Core Invariant & State Lifecycle

Core Invariant Specification

Everything on my stack is still waiting for an answer, and it is ordered. When a new element arrives, it answers every waiting element it beats.

Boundary Model: Monotonic Stack & Nesting Stack

A monotonic stack never goes the wrong way, so a pop answers a question about the popped index. A nesting stack holds one saved state per open bracket.

Loop Invariant Termination

Monotonic: while stack and nums[i] > nums[stack[-1]]: stack.pop(). Nesting: push on an opening token, pop on the matching close.

The 4 Mental Models of Stack

Monotonic stacks, nesting stacks and stack design: name the model before coding.

1Encode and Decode Strings

Length-Prefix Encoding

Spot it when: A list of strings must travel as one string and come back exactly, and the strings may hold any character, so no separator can be kept out of them.

Mode 1 · Encode and Decode Strings

Python

1	class Codec:
2	"""Encode and Decode Strings: write each string's length and a "#" in front of it.
3	Time: O(N + L) \| Space: O(N + L)
4	"""
5
6	def encode(self, strs: list[str]) -> str:
7	parts: list[str] = [] # One size-prefixed piece per string
8	for s in strs:
9	# 1. Write Each String's Size Before Its Data:
10	# Any character may appear inside a string, so no separator is safe; the reader learns where
11	# a piece ends before it reads a single character of it.
12	parts.append(str(len(s)) + "#" + s)
13	return "".join(parts)
14
15	def decode(self, s: str) -> list[str]:
16	strs: list[str] = []
17	i = 0 # Always the first digit of a length
18	while i < len(s):
19	# 1. Find Where The Size Ends:
20	# The first "#" from i must end the length, because digits written by encode never contain a "#".
21	j = s.index("#", i)
22	length = int(s[i:j])
23
24	# 2. Take Exactly That Many Characters And Jump Past Them:
25	# Counting instead of searching means a "#" or a digit inside the text is never read as part
26	# of the format.
27	strs.append(s[j + 1 : j + 1 + length])
28	i = j + 1 + length
29	return strs

Any character can appear inside a string, so no separator can mark where one ends: write the size before the data instead, str(len(s)) + "#" + s in encode. Digits never contain a "#", so in decode the first "#" from i, j = s.index("#", i), is exactly where the length ends, and the length says where the text ends: take s[j + 1 : j + 1 + length] and jump i = j + 1 + length without reading the text, so the next piece starts on a length again. The trap is reading the text by searching for the next "#" or splitting the message on "#": the strings may hold "#" and digits themselves, as in ["4#ab", "", "#"], and only counting length characters gets past them safely.

Gotchas1 of 4

The trap
Gotcha 1: Splitting the message on "#"
Mistake
```
def encode(self, strs):
    return "#".join(strs)

def decode(self, s):
    return s.split("#")
```
Fix
```
strs.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
```
What happens: Any character can appear inside a string, "#" included. A split on "#" cuts such a string into pieces. Reading up to the next "#" cuts it in the same way. decode must take exactly length characters and jump over them with i = j + 1 + length.
Example: strs = ["4#ab", "", "#"]
Mistake: returns ['4', 'ab', '', '', '']Fix: returns ['4#ab', '', '#']
Gotcha 2: Skipping empty strings in encode
Mistake
```
if s:
    parts.append(str(len(s)) + "#" + s)
```
Fix
```
parts.append(str(len(s)) + "#" + s)
```
What happens: An empty string is still one of the strings. It must come back from decode. encode writes it as "0#", a length with no text after it. Skipping it drops it from the result.
Example: strs = [""]
Mistake: returns []Fix: returns ['']
Gotcha 3: Searching with s.index("#") instead of s.index("#", i)
Mistake
```
j = s.index("#")
```
Fix
```
j = s.index("#", i)
```
What happens: Without i, the search starts at the beginning of the message every time. It finds the first "#" again, which ends the first length. For the second string, s[i:j] is then empty, and int("") raises a ValueError.
Example: strs = ["ab", "cd"]
Mistake: raises ValueErrorFix: returns ['ab', 'cd']
Gotcha 4: Reading one digit of the length with int(s[i])
Mistake
```
length = int(s[i])
```
Fix
```
length = int(s[i:j])
```
What happens: A string of 10 or more characters has a length of two or more digits. int(s[i]) reads only the first digit. decode then takes too few characters and loses its place in the message. The next search for "#" finds none and raises a ValueError.
Example: strs = ["abcdefghij"]
Mistake: raises ValueErrorFix: returns ['abcdefghij']

Canonical LeetCode:Encode and Decode Strings (LC 271)

Open the Encode and Decode Strings card

2Nesting Stack

nested input ➔ push the outer context on open ➔ pop and combine on close

Stack for Parsing & Nesting (Decode String, Basic Calculator)

Spot it when: The input nests: brackets inside brackets, a sub-expression inside parentheses, a folder inside a folder, and each inner part has to be finished before the part around it can go on.

Mode 2 · Nesting Stack

Python

1	def decode_string(s: str) -> str:
2	"""Decode String: save the outer text and count at each '[', restore them at ']'.
3	Time: O(N * L) \| Space: O(N + L)
4	"""
5	stack: list[tuple[str, int]] = [] # One saved (cur, num) per '[' still open
6	cur = "" # Text of the innermost open bracket, built so far
7	num = 0 # Repeat count being read, digit by digit
8
9	for ch in s:
10	if ch.isdigit():
11	# 1. Build The Repeat Count Digit By Digit:
12	# A count can have several digits, as in "12[a]", so each new digit shifts the earlier
13	# ones left by one place.
14	num = num * 10 + int(ch)
15	elif ch == "[":
16	# 2. Opener: Save The Outer State, Then Start The Inner One Empty:
17	# The outer text waits on stack with the count this bracket will use; resetting cur and num
18	# keeps the inner text from starting with the outer text already in it.
19	stack.append((cur, num))
20	cur, num = "", 0
21	elif ch == "]":
22	# 3. Closer: Restore The Outer State And Fold The Finished Inner Result In:
23	# The ']' closes the most recent '[', whose saved pair sits on top of stack; the inner text
24	# goes back after the outer text, repeated k times.
25	prev, k = stack.pop()
26	cur = prev + cur * k
27	else:
28	# 4. Plain Content Extends The Current Text:
29	# A letter belongs to whichever bracket is open right now.
30	cur += ch
31
32	return cur

A [ starts a smaller problem inside the current one, and the outer text has to wait until that inner problem is finished: so at [ push the outer state (cur, num) onto stack and start the inner text empty, and at ] pop it back and fold the finished inner text in with cur = prev + cur * k. Brackets close in the reverse order they open, so the ] you meet always closes the most recent [ still open, and the top of stack is exactly what that [ saved; everything below it waits untouched for its own ]. That is the whole model for any nesting (brackets, parentheses, folders): last opened, first finished, one saved context per open level. The trap is the reset: stack.append((cur, num)) must be followed by cur, num = "", 0. Keep the old cur and the outer text is repeated inside the bracket ("3[a2[c]]" turns into "aacacaacacaacac"); keep the old num and the next count's digits are glued onto it (the inner 2 is read as 32).

Gotchas1 of 5

The trap
Gotcha 1: Keeping the old cur after the push
Mistake
```
num = 0
```
Fix
```
cur, num = "", 0
```
What happens: At [, the outer text is saved on stack with stack.append((cur, num)). The inner text must then start empty. If cur keeps the outer text, that text is also repeated inside the bracket. At ], the outer text is added once more from stack.
Example: s = "3[a2[c]]"
Mistake: returns 'aacacaacacaacac'Fix: returns 'accaccacc'
Gotcha 2: Reading a count with num = int(ch)
Mistake
```
num = int(ch)
```
Fix
```
num = num * 10 + int(ch)
```
What happens: A count can have several digits, as in "10[a]". num = int(ch) keeps only the last digit. For "10[a]", num becomes 1 and then 0. The letter a is then repeated 0 times.
Example: s = "10[a]"
Mistake: returns ''Fix: returns 'aaaaaaaaaa'
Gotcha 3: Keeping the old num after the push
Mistake
```
cur = ""
```
Fix
```
cur, num = "", 0
```
What happens: At [, the count is saved on stack together with cur. If num keeps its value, the next count's digits are added after it. In "1[2[a]]", the inner count 2 is read as 12. The letter a is then repeated 12 times instead of 2.
Example: s = "1[2[a]]"
Mistake: returns 'aaaaaaaaaaaa'Fix: returns 'aa'
Gotcha 4: Reading stack[-1] instead of popping at ]
Mistake
```
prev, k = stack[-1]
```
Fix
```
prev, k = stack.pop()
```
What happens: Each ] closes the most recent open [. Its saved pair must leave stack with it. stack[-1] reads the pair but leaves it on stack. The next ] then uses the same saved pair a second time.
Example: s = "3[a2[c]]"
Mistake: returns 'aaccacc'Fix: returns 'accaccacc'
Gotcha 5: Folding with cur * k + prev
Mistake
```
cur = cur * k + prev
```
Fix
```
cur = prev + cur * k
```
What happens: prev is the text that came before the [. So it must come first in the result. cur * k + prev puts the repeated inner text before it.
Example: s = "a2[c]"
Mistake: returns 'cca'Fix: returns 'acc'

Canonical LeetCode:Decode String (LC 394)Valid Parentheses (LC 20)Longest Valid Parentheses (LC 32)Evaluate Reverse Polish Notation (LC 150)Simplify Path (LC 71)Basic Calculator (LC 224)

Open the Nesting Stack card

3Min-Stack Trick

push / pop stream ➔ each entry stores the running min with it ➔ O(1) query

Augmented Entries (Store a Running Min/Max/Count With Each Item)

Spot it when: A stack (or a queue) must answer a question about all of its contents, such as the minimum, the maximum or a running count, in O(1) per call while items are pushed and popped.

Mode 3 · Min-Stack Trick

Python

1	class MinStack:
2	"""Min Stack: each entry carries the minimum of itself and every entry below it.
3	Time: O(1) per call \| Space: O(N)
4	"""
5
6	def __init__(self) -> None:
7	# self.stack: one (val, current_min) pair per pushed value; current_min is the minimum of val
8	# and every entry below it, so the top entry always knows the whole stack's minimum.
9	self.stack: list[tuple[int, int]] = []
10
11	def push(self, val: int) -> None:
12	# 1. Compute This Entry's Running Minimum:
13	# Extend the minimum carried by the entry below with val, or start fresh when the stack is empty.
14	if self.stack:
15	current_min = min(val, self.stack[-1][1])
16	else:
17	current_min = val
18
19	# 2. Store The Value Together With Its Running Minimum:
20	# Pairing them means nothing below this entry has to change while it stays on the stack.
21	self.stack.append((val, current_min))
22
23	def pop(self) -> None:
24	self.stack.pop() # The new top already carries the minimum of what is left
25
26	def top(self) -> int:
27	return self.stack[-1][0]
28
29	def getMin(self) -> int:
30	return self.stack[-1][1] # Read it off the top entry: no search

A stack only changes at its top, so store with each entry the answer for itself and everything below it: push appends (val, current_min) with current_min = min(val, self.stack[-1][1]), and getMin just reads self.stack[-1][1]. While an entry sits on the stack nothing below it can change, so its current_min stays true until the entry itself is popped; pop removes exactly one entry, and the new top already carries the minimum of what is left, so nothing is ever recomputed. The same move carries any value you can build from the entry below: a maximum, a count or a pending increment. The trap is keeping one self.min for the whole stack: it is right after every push, but when pop removes the smallest value it can't know the next smallest without a scan.

Gotchas1 of 4

The trap
Gotcha 1: Keeping one self.min for the whole stack
Mistake
```
def getMin(self) -> int:
    return self.min
```
Fix
```
def getMin(self) -> int:
    return self.stack[-1][1]
```
What happens: One variable self.min is correct after every push. When pop removes the smallest value, self.min still holds it. Finding the next smallest value would need a scan of the whole stack. Each entry's own current_min already holds that value.
Example: push(-2), push(0), push(-3), pop(), getMin()
Mistake: returns -3Fix: returns -2
Gotcha 2: Comparing val with the value below, not its minimum
Mistake
```
current_min = min(val, self.stack[-1][0])
```
Fix
```
current_min = min(val, self.stack[-1][1])
```
What happens: self.stack[-1][0] is only the value just below. A smaller value may sit further down. self.stack[-1][1] is the minimum of every entry below. After pushing 1, 5 and 3, the value below 3 is 5. So current_min becomes 3 instead of 1.
Example: push(1), push(5), push(3), getMin()
Mistake: returns 3Fix: returns 1
Gotcha 3: Reading self.stack[-1] on the first push
Mistake
```
current_min = min(val, self.stack[-1][1])
```
Fix
```
if self.stack:
    current_min = min(val, self.stack[-1][1])
else:
    current_min = val
```
What happens: On the first push, self.stack is empty. It has no top entry to read. self.stack[-1] then raises an IndexError. The first entry is its own minimum, so current_min = val.
Example: push(5), getMin()
Mistake: raises IndexErrorFix: returns 5
Gotcha 4: Returning the carried minimum from top
Mistake
```
return self.stack[-1][1]
```
Fix
```
return self.stack[-1][0]
```
What happens: Each entry is a pair (val, current_min). top must return the value, which is at index 0. Index 1 holds the minimum. After push(-2) and push(0), top() must return 0, not -2.
Example: push(-2), push(0), top()
Mistake: returns -2Fix: returns 0

Canonical LeetCode:Min Stack (LC 155)Design a Stack With Increment Operation (LC 1381)Remove All Adjacent Duplicates in String II (LC 1209)Online Stock Span (LC 901)Maximum Frequency Stack (LC 895)

Open the Min-Stack Trick card

4Next Greater Element

stream of values ➔ stack of strictly decreasing indices ➔ pop on violation

Monotonic Stack (Next Greater Element)

Spot it when: For each element you need the next (or previous) greater or smaller element, or how far away it is.

Mode 4 · Next Greater Element

Python

1	from typing import Callable, List, Sequence, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def next_greater(values: Sequence[Item], pops: Callable[[Item, Item], bool]) -> List[int]:
7	"""Next Greater Element: for each index, the first later index whose value answers it, or -1.
8	pops(top, value) is True when value answers the waiting value top, for example top < value.
9	Precondition: when value does not pop the top of the stack, it pops no index below the top either.
10	This holds for the comparisons <, <=, > and >=.
11	132 Pattern and Online Stock Span (a class that answers one value at a time) do not fit.
12	N = len(values). T = the cost of one pops call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	n = len(values)
16	answer = [-1] * n # -1: no later value answers this index
17	stack: List[int] = [] # Holds INDICES of values still waiting for an answer, newest on top
18
19	# 1. Visit Each Value Left To Right:
20	# Scanning once suffices because an index can only be answered by a later index, so by the time value is reached, every index that could answer it has already arrived.
21	for i, value in enumerate(values):
22	# 2. Resolve Every Waiting Index That `pops` Answers:
23	# While value answers the index on top of the stack, pop it and record i as its answer. The precondition guarantees that once value stops answering the top, it cannot answer anything buried below it either, so the while loop can stop there.
24	while stack and pops(values[stack[-1]], value):
25	prev_idx = stack.pop() # Answered by the current value
26	answer[prev_idx] = i
27	# 3. Push The Current Index As Still Waiting:
28	# Whatever remains unanswered after the pops above is now the newest index waiting for its own answer, so it goes on top.
29	stack.append(i)
30
31	# 4. Return The Collected Answers:
32	# Any index left on the stack when the scan ends never found a later value that answers it, so it keeps its -1.
33	return answer

Keep stack as the indices still waiting for a warmer day, and when temp beats the temperature on top, i is that index's answer: pop it and write answer[prev_idx] = i - prev_idx. Every index below the top has a temperature at least as high as the top's, so if temp does not beat the top it cannot beat anything below it; each index is therefore answered by the first warmer day to its right, and never earlier. The trap is storing temperatures instead of indices: the answer is a distance written into its own slot of answer, so push i, not temp.

Gotchas1 of 4

The trap
Gotcha 1: Pushing temp instead of the index i
Mistake
```
stack.append(temp)
```
Fix
```
stack.append(i)
```
What happens: The answer is a distance, i - prev_idx, written into answer[prev_idx]. Both need the day's index, and a temperature cannot give it. With temp on stack, the loop reads temperatures[stack[-1]] with a temperature as the index. That index is past the end of the list, so Python raises an IndexError.
Example: temperatures = [30, 40, 50, 60]
Mistake: raises IndexErrorFix: returns [1, 1, 1, 0]
Gotcha 2: Filling answer with -1 instead of 0
Mistake
```
answer = [-1] * n
```
Fix
```
answer = [0] * n
```
What happens: Indices still on stack at the end never found a warmer day. The loop never writes their slot, so they keep the starting value. Daily Temperatures (LC 739) wants 0 for them. Next Greater Element I (LC 496) wants -1 instead.
Example: temperatures = [30, 60, 90]
Mistake: returns [1, 1, -1]Fix: returns [1, 1, 0]
Gotcha 3: Comparing the index stack[-1] with temp
Mistake
```
while stack and stack[-1] < temp:
```
Fix
```
while stack and temperatures[stack[-1]] < temp:
```
What happens: stack holds indices, so stack[-1] is a day number. Comparing a day number with a temperature has no meaning. The loop pops days that are not warmer and writes wrong distances. Read the temperature with temperatures[stack[-1]] first.
Example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Mistake: returns [1, 1, 1, 1, 1, 1, 1, 0]Fix: returns [1, 1, 4, 2, 1, 1, 0, 0]
Gotcha 4: Popping on <= when only a warmer day counts
Mistake
```
while stack and temperatures[stack[-1]] <= temp:
```
Fix
```
while stack and temperatures[stack[-1]] < temp:
```
What happens: Daily Temperatures (LC 739) asks for a strictly warmer day. With <=, a day with the same temperature pops the earlier day. The earlier day then gets the distance to a day that is not warmer.
Example: temperatures = [70, 70, 71]
Mistake: returns [1, 1, 0]Fix: returns [2, 1, 0]

Canonical LeetCode:Next Greater Element I (LC 496)Daily Temperatures (LC 739)Buildings With an Ocean View (LC 1762)Number of Valid Subarrays (LC 1063)The Number of Weak Characters in the Game (LC 1996)Car Fleet (LC 853)

Open the Next Greater Element card

Built on the mental models above

Valley WaterMonotonic Stack (Trapping Rain Water)
A pop closes a valley: the popped bar is the floor, the new top is the left wall and the arriving bar is the right wall.
Histogram StackMonotonic Stack (Largest Rectangle in Histogram)
A pop also needs the previous smaller bar, so the width is known at the moment the bar is popped.
Contribution TechniqueContribution Technique (Sum over All Subarrays via Each Element's Share)
Each popped item is the minimum of the range between its two smaller neighbours, so it counts value times left times right.
Lexicographic StackMonotonic Stack Greedy (Remove K Digits, Remove Duplicate Letters)
A pop is paid for by a budget of removals, or blocked because the popped item appears again later.

The Stack Decision Rule

When facing an unseen stack problem, ask in this order:

Step 1.Does the problem ask for the next warmer day, next greater/smaller element, or stock span?

➔ Next Greater Element

Next Greater Element I (LC 496)Daily Temperatures (LC 739)

Store indices in decreasing stack and pop when larger element arrives.

Step 2.Does the problem calculate rectangular histogram area?

➔ Histogram Stack

Largest Rectangle in Histogram (LC 84)Maximal Rectangle (LC 85)

Compute area with popped height and left/right stack boundaries.

Step 3.Do you need a sum or count over all subarrays of their minimum or maximum, with n too large for O(n^2)?

➔ Contribution Technique

Sum of Subarray Minimums (LC 907)Sum of Subarray Ranges (LC 2104)

Element i is the minimum of (i - left[i]) * (right[i] - i) subarrays; find left and right with a monotonic stack, breaking ties on one side only.

Step 4.Must you delete characters and keep the rest in order, so what is left is the smallest (or largest) number or string?

➔ Lexicographic Stack

Remove K Digits (LC 402)Remove Duplicate Letters (LC 316)

While deletions remain and the stack top is bigger than the current character, pop it; then push.

Step 5.Must a stack (or queue) answer the minimum, maximum or a running count of its contents in O(1) per call?

➔ Min-Stack Trick

Min Stack (LC 155)Design a Stack With Increment Operation (LC 1381)

Push (value, running min) pairs, so each entry remembers the answer for the stack below it.

Step 6.Does the input nest (brackets inside brackets, sub-expressions, folders), so each inner part must finish first?

➔ Nesting Stack

Decode String (LC 394)Valid Parentheses (LC 20)

On an opening token push the outer context; on the matching close pop it and combine it with the finished inner result.

Step 7.Must a list of arbitrary strings travel as one string and come back exactly?

➔ Encode and Decode Strings

Encode and Decode Strings (LC 271)

Write each string as its length, a delimiter, then the string; the decoder reads the length first.

Step 8.Must you add up the water (or the space) that a row of bars holds between taller bars?

➔ Valley Water

Trapping Rain Water (LC 42)

Pop each valley floor when a taller bar arrives; the new top is the left wall, so add width times the lower wall minus the floor.

Pattern Architecture & Invariant Design Masterclass

One idea runs through every card here: keep a stack of items that are still waiting, and let each new item answer the ones it can.

Monotonic stack. Asked "for each element, what is the next bigger one to its right?", the instinct is again O(n²). Instead keep a stack of elements still waiting for their answer, deliberately maintained so it is always increasing (or always decreasing). When a new element arrives, it answers every waiting element it beats — those get popped, permanently. Each element is pushed once and popped once, so the whole thing is O(n) despite the inner loop.

Nesting stack. Some inputs nest: brackets inside brackets, a sub-expression inside parentheses. Keep one saved state for each bracket that is still open, with the innermost on top. An opening token pushes the outer state. The matching close pops it and combines it with the inner result.

The Duplicate Asymmetry Invariant (Strict vs. Non-Strict Inequalities)

When using a monotonic stack to compute span boundaries over arrays that may contain duplicate elements and every subarray must be counted exactly once (e.g. Sum of Subarray Minimums), a subtle correctness bug emerges if both boundaries use the same comparison:

If both left and right boundaries use strict inequality (<), any subarray containing equal minimum values is counted twice.
If both boundaries use non-strict inequality (<=), equal elements pop each other prematurely, leaving duplicate spans uncounted.
The Invariant: Break symmetry deterministically. Set one side to strictly greater/smaller (<) and the opposite side to greater/smaller or equal (<=). This guarantees every contiguous subarray has a single, uniquely designated representative element (e.g. the leftmost minimum).
When nothing is counted: for a maximum such as Largest Rectangle in Histogram, letting a bar extend over equal heights on both sides is also correct; only stopping at equal heights on both sides is wrong, because the widest rectangle of that height is then never measured.

The invariants to say out loud:

Monotonic stack: "Everything on my stack is still waiting for an answer, and it is ordered — so the first element that fails the pop test means every one below it fails too. When duplicates exist, enforce asymmetric boundaries to partition spans uniquely."
Nesting stack: "The stack holds one saved state for every bracket that is still open, and the innermost is on top."

How this plays out in actual problems:

🟣 Scenario C: Monotonic Stack Pending Query Resolution (Indices Stack)

In nearest greater/smaller element queries (like Daily Temperatures LC 739 or Largest Rectangle in Histogram LC 84), pairwise lookups are $O(N^2)$ .
The Rule: Maintain an index stack maintaining strict monotonic order. An incoming element serves as the answer ("next greater/smaller") for every element it violates on top of the stack. Pop and record results in $O(1)$ amortized time.
The Code: while stack and val > arr[stack[-1]]: prev = stack.pop(); ans[prev] = i - prev

💡 The Ultimate Takeaway Decision Rule:
When analyzing a sequence query problem, ask: "Does each item need the nearest bigger or smaller item, does the input nest, or must a stack answer a question about all of its items?"

Nearest Greater / Smaller Element ➔ Monotonic stack of indices, pop on monotonic violation ( $O(N)$ ).

Max Rectangular Bounded Area ➔ Monotonic increasing stack with sentinel zero padding ( $O(N)$ ).

Nested Brackets or Expressions ➔ Push the saved state on an open token, pop on the close ( $O(N)$ ).

Running Minimum of a Stack ➔ Store the minimum with every entry ( $O(1)$ per call).

🌡️ 4. Monotonic Decreasing Stack for Next Greater Element (LC 739)

Mental Model: The stack stores indices of elements waiting for a higher temperature. Incoming higher temperature resolves all smaller elements below it.
Code: see the Next Greater Element card.

📊 5. Monotonic Increasing Stack for Histogram Bounded Area (LC 84)

Mental Model: A rectangle's height is determined by the shortest bar inside it. Popping a bar from an increasing stack identifies its left smaller boundary (stack[-1]) and right smaller boundary (i).
Code: see the Histogram Stack card.

Understanding Invariants: Monotonic Stack Pending Query Resolution

Everything on my stack is still waiting for an answer, and the stack never goes the wrong way.

Monotonic stacks maintain strict extremum order, so an incoming violator resolves every pending query it beats in amortized O(1) per element. Nesting stacks save one state per open level and restore it on the matching close.

Monotonic Stack Pending Resolution Invariant

Condition: While stack and val > arr[stack[-1]] (for next greater)

Action: prev = stack.pop(); ans[prev] = i - prev

Incoming element acts as the closest boundary or answer for all dominated waiting elements on the stack.

Nesting Stack Restore Invariant

Condition: On the matching close token

Action: outer_text, repeat = stack.pop(); cur = outer_text + repeat * cur

The popped entry is exactly the state that was saved when this bracket opened, so the inner result combines with the right outer state.

Common Questions

"My monotonic stack solution has a while loop nested inside a for loop — doesn't that make it O(n^2), the same as the brute force it's supposed to replace?"

It looks that way from the code's shape, but shape is misleading here — you have to track what each individual element does across the entire run, not what the inner loop does in one iteration of the outer loop.

The for loop runs n times, no argument there. The while loop's total iteration count across the whole algorithm is the part that's easy to miscount: every single element is pushed onto the stack exactly once (that happens once per for iteration, unconditionally) and popped at most once, ever — once an element is popped, it's answered and gone for good, it never goes back on the stack. So the grand total of all while-loop pops, summed over every iteration of the for loop, cannot exceed n — the same n elements that were pushed.

That gives at most n pushes plus at most n pops, 2n total stack operations, however unevenly they're distributed across iterations (one iteration might pop five elements, the next might pop zero). This is amortized analysis: the while loop isn't O(n) per outer iteration, it's O(n) for the entire algorithm, which is what makes the whole thing O(n) overall rather than O(n²). The tell an interviewer is listening for: "each element is pushed once and popped at most once."

Coach discussion points

1.
"Your monotonic stack has a while inside a for. Convince me it is not O(n²)." — The amortisation argument again. Follow up with "how many times in total can an index be popped?" if they stall.
2.
"Trapping Rain Water also has a two-pointer solution. Walk me through why the monotonic-stack version resolves a bar's water differently, and which one you'd actually reach for in an interview." — Tests whether the candidate understands both lenses on the same problem rather than having memorized one path, and whether they can articulate the trade-off (stack needs O(n) space; two-pointer needs O(1)).
3.
"Your Trapping Rain Water stack popped a valley and the stack is now empty. What do you do, and why is that not a bug?" — Forces the candidate to state the empty-stack guard out loud: that valley has no left wall yet, contributes zero for now, and is correctly not pushed back.
4.
"For Maximal Rectangle, why can you call the exact same largestRectangleArea function you wrote for the histogram problem, completely unchanged, once per row?" — Tests whether the candidate sees the row-reduction insight as a genuine algorithmic reduction (histogram problem solved once, reused rows times) rather than coincidence.

Complexity analysis

Daily Temperatures — Time O(n), Space O(n). This one is worth defending carefully, because it contains a while inside a for and looks quadratic. Each index is pushed exactly once and popped at most once, so the total number of stack operations across the whole run is at most 2n. The inner loop is not O(n) per iteration — it is O(n) for the entire algorithm. That is the same amortisation argument as the sliding window in two-pointers.md, and interviewers ask for it in exactly the same way. Space is the stack, O(n) when temperatures are strictly decreasing and nothing ever resolves.

Trapping Rain Water (Monotonic Stack) — Time O(n), Space O(n). Same amortisation argument as Daily Temperatures: each bar index is pushed exactly once and popped at most once across the entire run, so total stack operations are bounded by 2n regardless of the nested while inside the for. Space is the stack, worst case O(n) for a strictly decreasing elevation profile where nothing ever resolves.

Maximal Rectangle (Row-Reduced Histogram) — Time O(rows * cols), Space O(cols). Each of the rows rows costs O(cols) to update the running heights array, plus another amortised O(cols) to run the Largest Rectangle in Histogram (LC 84) solver on it — so the total is rows * O(cols) = O(rows * cols). Space is O(cols) for the persisted heights array plus the per-row monotonic stack (discarded after each row), independent of rows.

Production Systems Deployment & Motivation

A weather app shows, for each day, how many days until it gets warmer. A trading dashboard shows how long ago the price was last higher. Both need the nearest bigger value on one side of every item. Checking every later item for every item costs O(n²) and is too slow for a year of daily data. One pass with a stack costs O(n).

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if popping from a stack feels unintuitive right now! A stack turns quadratic searches into one linear pass because each item is pushed once and popped at most once. As you work through the cards, the same three questions repeat: what do I store, when do I pop, and what does a pop answer.

Pushing values when you also need positions: this problem only needs values, because all values are distinct. Problems with repeated values or distances need indices on the stack (Daily Temperatures).
Scanning nums2 once per query: looking up each nums1[i] with a fresh scan costs O(n1 * n2). Build the whole answer table once, then read it.
Forgetting the default: a value that stays on the stack has no larger value to its right, so its answer is -1. Use dict.get(x, -1).

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "next greater or smaller element", "largest rectangle in a histogram", "remove k digits to make the smallest number", "decode nested brackets". Each one needs the most recent unfinished item, and a stack gives exactly that.

CONSTRAINTS & BOUNDS

Arrays of up to $10^5$ items. Every item is pushed once and popped at most once, so the cost is $O(N)$ . Checking every later item for every item costs $O(N^2)$ and is too slow.

FAANG PRODUCTION TRAPS & EDGE CASES

Pushing values when the answer needs positions (push indices); using < where <= is needed when values repeat; forgetting the items left on the stack after the loop; popping while the stack is empty.

Theory Context•Stack

Conceptual Foundation & Intuitive Analogy

Checking future days for each day's "next warmer day" is O(N²). A monotonic decreasing stack resolves all days in a single linear pass by storing unresolved cooler days until a warmer day arrives.

🧭 Conceptual Foundation & Pattern Intuition

If Day 2 is colder than Day 1, Day 2 cannot be Day 1's answer, but both Day 1 and Day 2 are now waiting for some future warmer day.
A Monotonic Decreasing Stack stores the indices of days that are still waiting for a warmer temperature.
When we iterate to day $i$ $i$ with temperature $T[i]$ $T [i]$ :
- While the stack is non-empty and $T[i] > T[\text{stack}[-1]]$ : day $i$ is the very first warmer day for the day at the top of the stack! We pop prev_idx = stack.pop() and record the waiting duration: answer[prev_idx] = i - prev_idx.
- We push index $i$ onto the stack.
Any day remaining on the stack when the loop terminates never found a warmer day, correctly remaining 0.

🎫 The Analogy: The Waiting Room for Outdoor Cafe Seating

🔑 Why It Works

Visual Blueprint & State Transition Model

Core Invariant Specification

Everything on my stack is still waiting for an answer, and it is ordered. When a new element arrives, it answers every waiting element it beats.

Boundary Model: Monotonic Stack & Nesting Stack

A monotonic stack never goes the wrong way, so a pop answers a question about the popped index. A nesting stack holds one saved state per open bracket.

Loop Invariant Termination

Monotonic: while stack and nums[i] > nums[stack[-1]]: stack.pop(). Nesting: push on an opening token, pop on the matching close.

The 4 Mental Models of Stack

Monotonic stacks, nesting stacks and stack design: name the model before coding.

1Encode and Decode Strings

Length-Prefix Encoding

Spot it when: A list of strings must travel as one string and come back exactly, and the strings may hold any character, so no separator can be kept out of them.

Mode 1 · Encode and Decode Strings

Python

1	class Codec:
2	"""Encode and Decode Strings: write each string's length and a "#" in front of it.
3	Time: O(N + L) \| Space: O(N + L)
4	"""
5
6	def encode(self, strs: list[str]) -> str:
7	parts: list[str] = [] # One size-prefixed piece per string
8	for s in strs:
9	# 1. Write Each String's Size Before Its Data:
10	# Any character may appear inside a string, so no separator is safe; the reader learns where
11	# a piece ends before it reads a single character of it.
12	parts.append(str(len(s)) + "#" + s)
13	return "".join(parts)
14
15	def decode(self, s: str) -> list[str]:
16	strs: list[str] = []
17	i = 0 # Always the first digit of a length
18	while i < len(s):
19	# 1. Find Where The Size Ends:
20	# The first "#" from i must end the length, because digits written by encode never contain a "#".
21	j = s.index("#", i)
22	length = int(s[i:j])
23
24	# 2. Take Exactly That Many Characters And Jump Past Them:
25	# Counting instead of searching means a "#" or a digit inside the text is never read as part
26	# of the format.
27	strs.append(s[j + 1 : j + 1 + length])
28	i = j + 1 + length
29	return strs

Gotchas1 of 4

The trap
Gotcha 1: Splitting the message on "#"
Mistake
```
def encode(self, strs):
    return "#".join(strs)

def decode(self, s):
    return s.split("#")
```
Fix
```
strs.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
```
What happens: Any character can appear inside a string, "#" included. A split on "#" cuts such a string into pieces. Reading up to the next "#" cuts it in the same way. decode must take exactly length characters and jump over them with i = j + 1 + length.
Example: strs = ["4#ab", "", "#"]
Mistake: returns ['4', 'ab', '', '', '']Fix: returns ['4#ab', '', '#']
Gotcha 2: Skipping empty strings in encode
Mistake
```
if s:
    parts.append(str(len(s)) + "#" + s)
```
Fix
```
parts.append(str(len(s)) + "#" + s)
```
What happens: An empty string is still one of the strings. It must come back from decode. encode writes it as "0#", a length with no text after it. Skipping it drops it from the result.
Example: strs = [""]
Mistake: returns []Fix: returns ['']
Gotcha 3: Searching with s.index("#") instead of s.index("#", i)
Mistake
```
j = s.index("#")
```
Fix
```
j = s.index("#", i)
```
What happens: Without i, the search starts at the beginning of the message every time. It finds the first "#" again, which ends the first length. For the second string, s[i:j] is then empty, and int("") raises a ValueError.
Example: strs = ["ab", "cd"]
Mistake: raises ValueErrorFix: returns ['ab', 'cd']
Gotcha 4: Reading one digit of the length with int(s[i])
Mistake
```
length = int(s[i])
```
Fix
```
length = int(s[i:j])
```
What happens: A string of 10 or more characters has a length of two or more digits. int(s[i]) reads only the first digit. decode then takes too few characters and loses its place in the message. The next search for "#" finds none and raises a ValueError.
Example: strs = ["abcdefghij"]
Mistake: raises ValueErrorFix: returns ['abcdefghij']

Canonical LeetCode:Encode and Decode Strings (LC 271)

Open the Encode and Decode Strings card

2Nesting Stack

nested input ➔ push the outer context on open ➔ pop and combine on close

Stack for Parsing & Nesting (Decode String, Basic Calculator)

Spot it when: The input nests: brackets inside brackets, a sub-expression inside parentheses, a folder inside a folder, and each inner part has to be finished before the part around it can go on.

Mode 2 · Nesting Stack

Python

1	def decode_string(s: str) -> str:
2	"""Decode String: save the outer text and count at each '[', restore them at ']'.
3	Time: O(N * L) \| Space: O(N + L)
4	"""
5	stack: list[tuple[str, int]] = [] # One saved (cur, num) per '[' still open
6	cur = "" # Text of the innermost open bracket, built so far
7	num = 0 # Repeat count being read, digit by digit
8
9	for ch in s:
10	if ch.isdigit():
11	# 1. Build The Repeat Count Digit By Digit:
12	# A count can have several digits, as in "12[a]", so each new digit shifts the earlier
13	# ones left by one place.
14	num = num * 10 + int(ch)
15	elif ch == "[":
16	# 2. Opener: Save The Outer State, Then Start The Inner One Empty:
17	# The outer text waits on stack with the count this bracket will use; resetting cur and num
18	# keeps the inner text from starting with the outer text already in it.
19	stack.append((cur, num))
20	cur, num = "", 0
21	elif ch == "]":
22	# 3. Closer: Restore The Outer State And Fold The Finished Inner Result In:
23	# The ']' closes the most recent '[', whose saved pair sits on top of stack; the inner text
24	# goes back after the outer text, repeated k times.
25	prev, k = stack.pop()
26	cur = prev + cur * k
27	else:
28	# 4. Plain Content Extends The Current Text:
29	# A letter belongs to whichever bracket is open right now.
30	cur += ch
31
32	return cur

Gotchas1 of 5

The trap
Gotcha 1: Keeping the old cur after the push
Mistake
```
num = 0
```
Fix
```
cur, num = "", 0
```
What happens: At [, the outer text is saved on stack with stack.append((cur, num)). The inner text must then start empty. If cur keeps the outer text, that text is also repeated inside the bracket. At ], the outer text is added once more from stack.
Example: s = "3[a2[c]]"
Mistake: returns 'aacacaacacaacac'Fix: returns 'accaccacc'
Gotcha 2: Reading a count with num = int(ch)
Mistake
```
num = int(ch)
```
Fix
```
num = num * 10 + int(ch)
```
What happens: A count can have several digits, as in "10[a]". num = int(ch) keeps only the last digit. For "10[a]", num becomes 1 and then 0. The letter a is then repeated 0 times.
Example: s = "10[a]"
Mistake: returns ''Fix: returns 'aaaaaaaaaa'
Gotcha 3: Keeping the old num after the push
Mistake
```
cur = ""
```
Fix
```
cur, num = "", 0
```
What happens: At [, the count is saved on stack together with cur. If num keeps its value, the next count's digits are added after it. In "1[2[a]]", the inner count 2 is read as 12. The letter a is then repeated 12 times instead of 2.
Example: s = "1[2[a]]"
Mistake: returns 'aaaaaaaaaaaa'Fix: returns 'aa'
Gotcha 4: Reading stack[-1] instead of popping at ]
Mistake
```
prev, k = stack[-1]
```
Fix
```
prev, k = stack.pop()
```
What happens: Each ] closes the most recent open [. Its saved pair must leave stack with it. stack[-1] reads the pair but leaves it on stack. The next ] then uses the same saved pair a second time.
Example: s = "3[a2[c]]"
Mistake: returns 'aaccacc'Fix: returns 'accaccacc'
Gotcha 5: Folding with cur * k + prev
Mistake
```
cur = cur * k + prev
```
Fix
```
cur = prev + cur * k
```
What happens: prev is the text that came before the [. So it must come first in the result. cur * k + prev puts the repeated inner text before it.
Example: s = "a2[c]"
Mistake: returns 'cca'Fix: returns 'acc'

Canonical LeetCode:Decode String (LC 394)Valid Parentheses (LC 20)Longest Valid Parentheses (LC 32)Evaluate Reverse Polish Notation (LC 150)Simplify Path (LC 71)Basic Calculator (LC 224)

Open the Nesting Stack card

3Min-Stack Trick

push / pop stream ➔ each entry stores the running min with it ➔ O(1) query

Augmented Entries (Store a Running Min/Max/Count With Each Item)

Spot it when: A stack (or a queue) must answer a question about all of its contents, such as the minimum, the maximum or a running count, in O(1) per call while items are pushed and popped.

Mode 3 · Min-Stack Trick

Python

1	class MinStack:
2	"""Min Stack: each entry carries the minimum of itself and every entry below it.
3	Time: O(1) per call \| Space: O(N)
4	"""
5
6	def __init__(self) -> None:
7	# self.stack: one (val, current_min) pair per pushed value; current_min is the minimum of val
8	# and every entry below it, so the top entry always knows the whole stack's minimum.
9	self.stack: list[tuple[int, int]] = []
10
11	def push(self, val: int) -> None:
12	# 1. Compute This Entry's Running Minimum:
13	# Extend the minimum carried by the entry below with val, or start fresh when the stack is empty.
14	if self.stack:
15	current_min = min(val, self.stack[-1][1])
16	else:
17	current_min = val
18
19	# 2. Store The Value Together With Its Running Minimum:
20	# Pairing them means nothing below this entry has to change while it stays on the stack.
21	self.stack.append((val, current_min))
22
23	def pop(self) -> None:
24	self.stack.pop() # The new top already carries the minimum of what is left
25
26	def top(self) -> int:
27	return self.stack[-1][0]
28
29	def getMin(self) -> int:
30	return self.stack[-1][1] # Read it off the top entry: no search

Gotchas1 of 4

The trap
Gotcha 1: Keeping one self.min for the whole stack
Mistake
```
def getMin(self) -> int:
    return self.min
```
Fix
```
def getMin(self) -> int:
    return self.stack[-1][1]
```
What happens: One variable self.min is correct after every push. When pop removes the smallest value, self.min still holds it. Finding the next smallest value would need a scan of the whole stack. Each entry's own current_min already holds that value.
Example: push(-2), push(0), push(-3), pop(), getMin()
Mistake: returns -3Fix: returns -2
Gotcha 2: Comparing val with the value below, not its minimum
Mistake
```
current_min = min(val, self.stack[-1][0])
```
Fix
```
current_min = min(val, self.stack[-1][1])
```
What happens: self.stack[-1][0] is only the value just below. A smaller value may sit further down. self.stack[-1][1] is the minimum of every entry below. After pushing 1, 5 and 3, the value below 3 is 5. So current_min becomes 3 instead of 1.
Example: push(1), push(5), push(3), getMin()
Mistake: returns 3Fix: returns 1
Gotcha 3: Reading self.stack[-1] on the first push
Mistake
```
current_min = min(val, self.stack[-1][1])
```
Fix
```
if self.stack:
    current_min = min(val, self.stack[-1][1])
else:
    current_min = val
```
What happens: On the first push, self.stack is empty. It has no top entry to read. self.stack[-1] then raises an IndexError. The first entry is its own minimum, so current_min = val.
Example: push(5), getMin()
Mistake: raises IndexErrorFix: returns 5
Gotcha 4: Returning the carried minimum from top
Mistake
```
return self.stack[-1][1]
```
Fix
```
return self.stack[-1][0]
```
What happens: Each entry is a pair (val, current_min). top must return the value, which is at index 0. Index 1 holds the minimum. After push(-2) and push(0), top() must return 0, not -2.
Example: push(-2), push(0), top()
Mistake: returns -2Fix: returns 0

Canonical LeetCode:Min Stack (LC 155)Design a Stack With Increment Operation (LC 1381)Remove All Adjacent Duplicates in String II (LC 1209)Online Stock Span (LC 901)Maximum Frequency Stack (LC 895)

Open the Min-Stack Trick card

4Next Greater Element

stream of values ➔ stack of strictly decreasing indices ➔ pop on violation

Monotonic Stack (Next Greater Element)

Spot it when: For each element you need the next (or previous) greater or smaller element, or how far away it is.

Mode 4 · Next Greater Element

Python

1	from typing import Callable, List, Sequence, TypeVar
2
3	Item = TypeVar("Item")
4
5
6	def next_greater(values: Sequence[Item], pops: Callable[[Item, Item], bool]) -> List[int]:
7	"""Next Greater Element: for each index, the first later index whose value answers it, or -1.
8	pops(top, value) is True when value answers the waiting value top, for example top < value.
9	Precondition: when value does not pop the top of the stack, it pops no index below the top either.
10	This holds for the comparisons <, <=, > and >=.
11	132 Pattern and Online Stock Span (a class that answers one value at a time) do not fit.
12	N = len(values). T = the cost of one pops call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	n = len(values)
16	answer = [-1] * n # -1: no later value answers this index
17	stack: List[int] = [] # Holds INDICES of values still waiting for an answer, newest on top
18
19	# 1. Visit Each Value Left To Right:
20	# Scanning once suffices because an index can only be answered by a later index, so by the time value is reached, every index that could answer it has already arrived.
21	for i, value in enumerate(values):
22	# 2. Resolve Every Waiting Index That `pops` Answers:
23	# While value answers the index on top of the stack, pop it and record i as its answer. The precondition guarantees that once value stops answering the top, it cannot answer anything buried below it either, so the while loop can stop there.
24	while stack and pops(values[stack[-1]], value):
25	prev_idx = stack.pop() # Answered by the current value
26	answer[prev_idx] = i
27	# 3. Push The Current Index As Still Waiting:
28	# Whatever remains unanswered after the pops above is now the newest index waiting for its own answer, so it goes on top.
29	stack.append(i)
30
31	# 4. Return The Collected Answers:
32	# Any index left on the stack when the scan ends never found a later value that answers it, so it keeps its -1.
33	return answer

Gotchas1 of 4

The trap
Gotcha 1: Pushing temp instead of the index i
Mistake
```
stack.append(temp)
```
Fix
```
stack.append(i)
```
What happens: The answer is a distance, i - prev_idx, written into answer[prev_idx]. Both need the day's index, and a temperature cannot give it. With temp on stack, the loop reads temperatures[stack[-1]] with a temperature as the index. That index is past the end of the list, so Python raises an IndexError.
Example: temperatures = [30, 40, 50, 60]
Mistake: raises IndexErrorFix: returns [1, 1, 1, 0]
Gotcha 2: Filling answer with -1 instead of 0
Mistake
```
answer = [-1] * n
```
Fix
```
answer = [0] * n
```
What happens: Indices still on stack at the end never found a warmer day. The loop never writes their slot, so they keep the starting value. Daily Temperatures (LC 739) wants 0 for them. Next Greater Element I (LC 496) wants -1 instead.
Example: temperatures = [30, 60, 90]
Mistake: returns [1, 1, -1]Fix: returns [1, 1, 0]
Gotcha 3: Comparing the index stack[-1] with temp
Mistake
```
while stack and stack[-1] < temp:
```
Fix
```
while stack and temperatures[stack[-1]] < temp:
```
What happens: stack holds indices, so stack[-1] is a day number. Comparing a day number with a temperature has no meaning. The loop pops days that are not warmer and writes wrong distances. Read the temperature with temperatures[stack[-1]] first.
Example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Mistake: returns [1, 1, 1, 1, 1, 1, 1, 0]Fix: returns [1, 1, 4, 2, 1, 1, 0, 0]
Gotcha 4: Popping on <= when only a warmer day counts
Mistake
```
while stack and temperatures[stack[-1]] <= temp:
```
Fix
```
while stack and temperatures[stack[-1]] < temp:
```
What happens: Daily Temperatures (LC 739) asks for a strictly warmer day. With <=, a day with the same temperature pops the earlier day. The earlier day then gets the distance to a day that is not warmer.
Example: temperatures = [70, 70, 71]
Mistake: returns [1, 1, 0]Fix: returns [2, 1, 0]

Open the Next Greater Element card

Built on the mental models above

Valley WaterMonotonic Stack (Trapping Rain Water)
A pop closes a valley: the popped bar is the floor, the new top is the left wall and the arriving bar is the right wall.
Histogram StackMonotonic Stack (Largest Rectangle in Histogram)
A pop also needs the previous smaller bar, so the width is known at the moment the bar is popped.
Contribution TechniqueContribution Technique (Sum over All Subarrays via Each Element's Share)
Each popped item is the minimum of the range between its two smaller neighbours, so it counts value times left times right.
Lexicographic StackMonotonic Stack Greedy (Remove K Digits, Remove Duplicate Letters)
A pop is paid for by a budget of removals, or blocked because the popped item appears again later.

The Stack Decision Rule

When facing an unseen stack problem, ask in this order:

Step 1.Does the problem ask for the next warmer day, next greater/smaller element, or stock span?

➔ Next Greater Element

Next Greater Element I (LC 496)Daily Temperatures (LC 739)

Store indices in decreasing stack and pop when larger element arrives.

Step 2.Does the problem calculate rectangular histogram area?

➔ Histogram Stack

Largest Rectangle in Histogram (LC 84)Maximal Rectangle (LC 85)

Compute area with popped height and left/right stack boundaries.

Step 3.Do you need a sum or count over all subarrays of their minimum or maximum, with n too large for O(n^2)?

➔ Contribution Technique

Sum of Subarray Minimums (LC 907)Sum of Subarray Ranges (LC 2104)

Element i is the minimum of (i - left[i]) * (right[i] - i) subarrays; find left and right with a monotonic stack, breaking ties on one side only.

Step 4.Must you delete characters and keep the rest in order, so what is left is the smallest (or largest) number or string?

➔ Lexicographic Stack

Remove K Digits (LC 402)Remove Duplicate Letters (LC 316)

While deletions remain and the stack top is bigger than the current character, pop it; then push.

Step 5.Must a stack (or queue) answer the minimum, maximum or a running count of its contents in O(1) per call?

➔ Min-Stack Trick

Min Stack (LC 155)Design a Stack With Increment Operation (LC 1381)

Push (value, running min) pairs, so each entry remembers the answer for the stack below it.

Step 6.Does the input nest (brackets inside brackets, sub-expressions, folders), so each inner part must finish first?

➔ Nesting Stack

Decode String (LC 394)Valid Parentheses (LC 20)

On an opening token push the outer context; on the matching close pop it and combine it with the finished inner result.

Step 7.Must a list of arbitrary strings travel as one string and come back exactly?

➔ Encode and Decode Strings

Encode and Decode Strings (LC 271)

Write each string as its length, a delimiter, then the string; the decoder reads the length first.

Step 8.Must you add up the water (or the space) that a row of bars holds between taller bars?

➔ Valley Water

Trapping Rain Water (LC 42)

Pop each valley floor when a taller bar arrives; the new top is the left wall, so add width times the lower wall minus the floor.

Pattern Architecture & Invariant Design Masterclass

One idea runs through every card here: keep a stack of items that are still waiting, and let each new item answer the ones it can.

The Duplicate Asymmetry Invariant (Strict vs. Non-Strict Inequalities)

If both left and right boundaries use strict inequality (<), any subarray containing equal minimum values is counted twice.
If both boundaries use non-strict inequality (<=), equal elements pop each other prematurely, leaving duplicate spans uncounted.
The Invariant: Break symmetry deterministically. Set one side to strictly greater/smaller (<) and the opposite side to greater/smaller or equal (<=). This guarantees every contiguous subarray has a single, uniquely designated representative element (e.g. the leftmost minimum).
When nothing is counted: for a maximum such as Largest Rectangle in Histogram, letting a bar extend over equal heights on both sides is also correct; only stopping at equal heights on both sides is wrong, because the widest rectangle of that height is then never measured.

The invariants to say out loud:

Monotonic stack: "Everything on my stack is still waiting for an answer, and it is ordered — so the first element that fails the pop test means every one below it fails too. When duplicates exist, enforce asymmetric boundaries to partition spans uniquely."
Nesting stack: "The stack holds one saved state for every bracket that is still open, and the innermost is on top."

How this plays out in actual problems:

🟣 Scenario C: Monotonic Stack Pending Query Resolution (Indices Stack)

In nearest greater/smaller element queries (like Daily Temperatures LC 739 or Largest Rectangle in Histogram LC 84), pairwise lookups are $O(N^2)$ .
The Rule: Maintain an index stack maintaining strict monotonic order. An incoming element serves as the answer ("next greater/smaller") for every element it violates on top of the stack. Pop and record results in $O(1)$ amortized time.
The Code: while stack and val > arr[stack[-1]]: prev = stack.pop(); ans[prev] = i - prev

💡 The Ultimate Takeaway Decision Rule:
When analyzing a sequence query problem, ask: "Does each item need the nearest bigger or smaller item, does the input nest, or must a stack answer a question about all of its items?"

Nearest Greater / Smaller Element ➔ Monotonic stack of indices, pop on monotonic violation ( $O(N)$ ).

Max Rectangular Bounded Area ➔ Monotonic increasing stack with sentinel zero padding ( $O(N)$ ).

Nested Brackets or Expressions ➔ Push the saved state on an open token, pop on the close ( $O(N)$ ).

Running Minimum of a Stack ➔ Store the minimum with every entry ( $O(1)$ per call).

🌡️ 4. Monotonic Decreasing Stack for Next Greater Element (LC 739)

Mental Model: The stack stores indices of elements waiting for a higher temperature. Incoming higher temperature resolves all smaller elements below it.
Code: see the Next Greater Element card.

📊 5. Monotonic Increasing Stack for Histogram Bounded Area (LC 84)

Mental Model: A rectangle's height is determined by the shortest bar inside it. Popping a bar from an increasing stack identifies its left smaller boundary (stack[-1]) and right smaller boundary (i).
Code: see the Histogram Stack card.

Understanding Invariants: Monotonic Stack Pending Query Resolution

Everything on my stack is still waiting for an answer, and the stack never goes the wrong way.

Monotonic Stack Pending Resolution Invariant

Condition: While stack and val > arr[stack[-1]] (for next greater)

Action: prev = stack.pop(); ans[prev] = i - prev

Incoming element acts as the closest boundary or answer for all dominated waiting elements on the stack.

Nesting Stack Restore Invariant

Condition: On the matching close token

Action: outer_text, repeat = stack.pop(); cur = outer_text + repeat * cur

The popped entry is exactly the state that was saved when this bracket opened, so the inner result combines with the right outer state.

Common Questions

"My monotonic stack solution has a while loop nested inside a for loop — doesn't that make it O(n^2), the same as the brute force it's supposed to replace?"

It looks that way from the code's shape, but shape is misleading here — you have to track what each individual element does across the entire run, not what the inner loop does in one iteration of the outer loop.

The for loop runs n times, no argument there. The while loop's total iteration count across the whole algorithm is the part that's easy to miscount: every single element is pushed onto the stack exactly once (that happens once per for iteration, unconditionally) and popped at most once, ever — once an element is popped, it's answered and gone for good, it never goes back on the stack. So the grand total of all while-loop pops, summed over every iteration of the for loop, cannot exceed n — the same n elements that were pushed.

That gives at most n pushes plus at most n pops, 2n total stack operations, however unevenly they're distributed across iterations (one iteration might pop five elements, the next might pop zero). This is amortized analysis: the while loop isn't O(n) per outer iteration, it's O(n) for the entire algorithm, which is what makes the whole thing O(n) overall rather than O(n²). The tell an interviewer is listening for: "each element is pushed once and popped at most once."

Coach discussion points

1.
"Your monotonic stack has a while inside a for. Convince me it is not O(n²)." — The amortisation argument again. Follow up with "how many times in total can an index be popped?" if they stall.
2.
"Trapping Rain Water also has a two-pointer solution. Walk me through why the monotonic-stack version resolves a bar's water differently, and which one you'd actually reach for in an interview." — Tests whether the candidate understands both lenses on the same problem rather than having memorized one path, and whether they can articulate the trade-off (stack needs O(n) space; two-pointer needs O(1)).
3.
"Your Trapping Rain Water stack popped a valley and the stack is now empty. What do you do, and why is that not a bug?" — Forces the candidate to state the empty-stack guard out loud: that valley has no left wall yet, contributes zero for now, and is correctly not pushed back.
4.
"For Maximal Rectangle, why can you call the exact same largestRectangleArea function you wrote for the histogram problem, completely unchanged, once per row?" — Tests whether the candidate sees the row-reduction insight as a genuine algorithmic reduction (histogram problem solved once, reused rows times) rather than coincidence.

Complexity analysis

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Pushing values when you also need positions: this problem only needs values, because all values are distinct. Problems with repeated values or distances need indices on the stack (Daily Temperatures).
Scanning nums2 once per query: looking up each nums1[i] with a fresh scan costs O(n1 * n2). Build the whole answer table once, then read it.
Forgetting the default: a value that stays on the stack has no larger value to its right, so its answer is -1. Use dict.get(x, -1).

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

Arrays of up to $10^5$ items. Every item is pushed once and popped at most once, so the cost is $O(N)$ . Checking every later item for every item costs $O(N^2)$ and is too slow.

FAANG PRODUCTION TRAPS & EDGE CASES