Topic 3: Stack

General Intuition #

• referring to the 2 pointers vs stack, we observe that stacks are useful to handle contextual info that is implicit and nested in a sequential manner.

• General Intuition on Monotonic stack pattern. It seems that usually, the in-consideration elements are the ones that we’re putting in the stack. They’re in there because we need to preserve some intermediate order of these in-consideration elements.

  • in some cases, we’re putting the unresolved elements in the monotonic stack.

  • this is also useful when we want to keep a history of considerations while we find boundaries for things. The history point rings true here.

  • the stack could also be the currently accumulated best value (e.g. like in the remove duplicates question)

Canonical Questions #

Nested / Contextual Structure: “open-until-closed” semantics #

• Key Idea: The problem involves matching pairs, nested blocks, or hierarchical structures that appear in a sequential but nested manner. The matching is done in a FILO fashion and that’s why using a stack is a natural outcome.

• Pattern: Use stack to maintain opening elements; resolve when closing elements appear. Classic FILO behaviour.

Problems #

1. Valid Parentheses (20) (matching brackets)

   Keep open braces until appropriate closer comes in, just merge them in asap. Our stack is keeping all the in-consideration state, which is just the openers (never the closers).

   This is a straightforward implementation, we just have to follow the process that they’ve outlined.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   class Solution: def isValid(self, s: str) -> bool: openerToCloser = {'(': ')', '{' : '}', '[': ']' } openers = openerToCloser.keys() closers = openerToCloser.values() # a list is fine here, append and pop run in O(1) stack = [] for elem in s: if len(stack) == 0 and elem in closers: return False if len(stack) == 0 and elem in openers: stack.append(elem) continue # non-empty stack cases: if elem in closers: is_matching_bracket = elem == openerToCloser[stack.pop()] if is_matching_bracket: continue else: # found mismatch return False if elem in openers: stack.append(elem) continue return not stack

   Code Snippet 1: Valid Parentheses (20)
   Pattern Extraction

   Core Insight: A stack naturally models nested structure — openers are pushed and must be matched by the correct closer in LIFO order. Pattern Name: Stack-Based Bracket Matching Canonical Section: Stack > Matching Brackets Recognition Signals:

   • Nested or hierarchical structure (brackets, tags, scopes)
   • Each opener must be matched by the corresponding closer in LIFO order
   • Validity depends on proper nesting, not just counts

   Anti-Signals:

   • Only counting brackets (equal openers and closers) — counter suffices, no stack needed
   • Brackets can be reordered — not a stack problem
   • “Valid parenthesis string” with wildcards — DP or greedy range tracking (LC 678)

   Decision Point: Multiple bracket types ([], (), {}) require a stack. Single bracket type (() only) can be solved with a counter.

   Pitfalls and Misconceptions

   1. Trap: Only counting openers and closers without checking matching types. Why: "([)]" has equal counts of each type but is invalid due to crossing nesting. Correction: Use a stack to enforce LIFO matching: the top of the stack must match the current closer.
   2. Trap: Forgetting to check if the stack is empty before popping when a closer arrives. Why: An unmatched closer with an empty stack causes an index error or wrong result. Correction: If stack is empty and a closer arrives, return False immediately.
   3. Trap: Not checking if the stack is empty at the end. Why: Unmatched openers remaining in the stack mean the string is invalid (e.g., "((" ). Correction: Return not stack (True only if stack is empty).
   Problem Mutations

   1. What if you needed to find the longest valid parentheses substring? (stress-tests: full-string validity) Stack tracks indices of unmatched brackets. The longest valid substring is the max gap between unmatched positions. Connects to LC 32 Longest Valid Parentheses.
   2. What if wildcards (*) could be opener, closer, or empty? (stress-tests: deterministic matching) Stack doesn’t work directly. Use two counters tracking the range of possible open-bracket counts. Connects to LC 678 Valid Parenthesis String.
   3. What if you needed to remove the minimum brackets to make it valid? (stress-tests: validation vs repair) Track indices of unmatched brackets using a stack, then remove those indices from the string. Connects to LC 1249 Minimum Remove to Make Valid Parentheses.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Valid Parentheses generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Evaluate Reverse Polish Notation (150)

   We keep tokens (in-consideration would be the operands) within the stack until we can form legitimate operands using them for a viable operator character. If we don’t have the right operands yet, then it can only mean that we’re deferring that operation, that’s how our in-consideration stack would grow (deferments).

   This question had the odd “division tends to zero” gotcha.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class Solution: def evalRPN(self, tokens: List[str]) -> int: fns = { '+': lambda a, b: a + b, '-': lambda a, b: a - b, '*': lambda a, b: a * b, '/': lambda a, b: int(a / b) # IMPORTANT:truncates towards zero } stack = [] for token in tokens: if token in fns: b = stack.pop() a = stack.pop() stack.append(fns[token](a, b)) else: stack.append(int(token)) return stack[0]

   Code Snippet 2: Evaluate Reverse Polish Notation (150)
   Pattern Extraction

   Core Insight: RPN eliminates ambiguity by placing operators after their operands; a stack accumulates operands until an operator consumes the top two. Pattern Name: Stack-Based Expression Evaluation Canonical Section: Stack > Matching Brackets / Expression Evaluation Recognition Signals:

   • Postfix (RPN) or infix expression evaluation
   • Operators consume the most recent operands (LIFO)
   • Need to handle operator precedence (for infix; RPN has none)

   Anti-Signals:

   • Expression is already a parse tree — traverse directly, no stack needed
   • Need to convert between notations (infix to postfix) — that’s Shunting Yard algorithm, a different stack problem

   Decision Point: RPN evaluation is the simplest stack expression problem. Infix evaluation requires precedence handling (Shunting Yard). Prefix evaluation processes right-to-left.

   Pitfalls and Misconceptions

   1. Trap: Using Python’s // for integer division instead of int(a / b). Why: Python’s // floors towards negative infinity: -7 // 2 = -4=. The problem specifies truncation towards zero: int(-7 / 2) = -3=. Correction: Use int(a / b) for truncation-towards-zero semantics.
   2. Trap: Popping operands in wrong order — a, b = stack.pop(), stack.pop() gives b first. Why: For non-commutative operations (subtraction, division), operand order matters. The first-pushed operand is the left operand. Correction: Pop b first (right operand), then a (left operand): b = stack.pop(); a = stack.pop().
   Problem Mutations

   1. What if the expression were infix instead of postfix? (stress-tests: notation type) Need Shunting Yard algorithm to handle operator precedence and parentheses. Much more complex. Connects to LC 224 Basic Calculator.
   2. What if the expression could contain variables that need to be resolved? (stress-tests: literal operands) Extend the operand parsing to include variable lookup from a symbol table. The stack logic is identical.
   3. What if the expression were malformed (too many/few operands)? (stress-tests: well-formed assumption) Check stack size after evaluation: should have exactly one element. Also check stack has at least 2 elements before each operator.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Evaluate Reverse Polish Notation generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Next Smaller/Greater Element \(\implies\) boundary finding #

• Key idea: For every element, find the nearest element to the left/right that is greater/smaller. Our stack will be the currently unresolved elements that we’re working with.

• Pattern:

  1. Maintain a monotonically increasing or decreasing stack of indices or elements.

  2. Pop from stack when current (in-consideration as the greater than for some other index) element breaks the monotonic property.

  3. Reasoning:

     The stack holds unresolved candidates in order so boundaries are efficiently found. It’s like there’s a bunch of things we need to do at once, we can keep an order to the unresolved ones so far and eventually our objective is to try resolve everything.

Problems #

1. Daily Temperatures (739)

   This is literally a direct “next greater element” question. We keep adding to the stack as long as we don’t dip in temperature. When we do dip, then flush the stack, everything is bounded by the value at the top of the stack.

   Invariant: This makes the stack always contain non-decreasing values (hence it’s a monotonically increasing stack), which are the in-consideration elements.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: res = [0] * len(temperatures) stack = [] for idx, temp in enumerate(temperatures): if not stack: stack.append((idx, temp)) continue # only start concluding once we see a dip: while can_conclude:=(stack and stack[-1][1] < temp): # today will be the next greatest for all the elements within the stack. start_idx, _ = stack.pop() days = idx - start_idx res[start_idx] = days # else, it's constantly increasing, keep accumulating it. stack.append((idx, temp)) return res

   Code Snippet 3: Daily Temperatures (739)
   Pattern Extraction

   Core Insight: A monotonic decreasing stack holds indices of “unresolved” temperatures; when a warmer day arrives, it resolves everything on the stack that it’s warmer than. Pattern Name: Monotonic Stack for Next Greater Element Canonical Section: Stack > Next Smaller/Greater Element Recognition Signals:

   • “Next greater/smaller element” for each position
   • “How many days until X” (distance to next satisfying element)
   • Need to find boundaries (left/right) for each element efficiently
   • \(O(n)\) time, each element pushed and popped at most once

   Anti-Signals:

   • Need the Kth greater element, not just the next one — monotonic stack gives only the nearest
   • Circular array — process array twice (double the length) to handle wrap-around (LC 503)
   • Need all greater elements, not just the next — different data structure

   Decision Point: “Next greater” = monotonic decreasing stack (pop when current > top). “Next smaller” = monotonic increasing stack (pop when current < top). The stack stores indices, not values, so you can compute distances. Interviewer Comms: “I maintain a monotonic decreasing stack of indices. For each new temperature, I pop all indices from the stack where the stored temperature is less than current — each popped index has found its next warmer day. Then I push the current index. Each element enters and exits the stack exactly once, so it’s \(O(n)\).”

   Pitfalls and Misconceptions

   1. Trap: Storing values in the stack instead of indices. Why: You need indices to compute the distance (“how many days until…”). Values alone don’t give positions. Correction: Push indices; access values via temperatures[stack[-1]].
   2. Trap: Using a monotonically increasing stack instead of decreasing. Why: For “next greater,” the stack must hold decreasing values so that a greater element triggers pops. An increasing stack would pop on smaller elements (next smaller element pattern). Correction: Pop when temperatures[i] > temperatures[stack[-1]].
   Problem Mutations

   1. What if the array were circular? (stress-tests: linear assumption) Process the array twice (indices 0 to 2n-1, using i % n). The second pass resolves elements that wrap around. Connects to LC 503 Next Greater Element II.
   2. What if you needed the next greater element’s VALUE instead of the distance? (stress-tests: output type) Same stack logic; just store the value at the resolution point instead of the distance. Connects to LC 496 Next Greater Element I.
   3. What if you needed the next SMALLER element instead of greater? (stress-tests: comparison direction) Flip the comparison: pop when temps[i] < temps[stack[-1]]. The stack becomes monotonically increasing.
   4. What if elements were being added online (streaming)? (stress-tests: static assumption) The monotonic stack naturally supports online processing — each new element triggers pops and then is pushed. Perfectly suited for streaming.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Daily Temperatures generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Largest Rectangle in Histogram (84) ⭐️

   This is one of the most classic monotonic stack questions.

   We have to identify contiguous segments that can form rectangles by going as left and right as possible for a particular segment of histogram bars.

   Heights are given, so the in-consideration bars can be tracked using their indices. So we store indices (in consideration) until we find the right boundary (the height dips), then we just flush until an upswing is found (current height >= heights[stack[-1]]).

   There’s also some nifty sentinel value-handling that is done in the solution below that is worth our attention. The sentinel case essentially allows us to

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class Solution: def largestRectangleArea(self, heights: List[int]) -> int: # we store indices and make decisions on the bars in this stack stack = [] max_area = 0 for i in range(len(heights) + 1): # ensures that the last bar is added to the stack curr_height = heights[i] if i < len(heights) else 0 # Sentinel: pops all at the end # the bar currently in consideration is always the bar at the top of the stack while (found_right_boundary:= stack and curr_height < heights[stack[-1]]): min_height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 max_area = max(max_area, min_height * width) # add the small left boundary stack.append(i) return max_area

   Code Snippet 4: Largest Rectangle in Histogram (84)
   Pattern Extraction

   Core Insight: For each bar, the largest rectangle using that bar as the shortest has width determined by the nearest shorter bars on both sides. A monotonic increasing stack finds both boundaries in a single pass. Pattern Name: Monotonic Stack for Span/Boundary Calculation Canonical Section: Stack > Next Smaller/Greater Element Recognition Signals:

   • Each element defines a constraint (height), and you need to find the range over which that constraint holds
   • “Largest rectangle” or “maximum span” under some monotonicity condition
   • Need left and right boundaries for each element
   • \(O(n)\) time required

   Anti-Signals:

   • Heights can change (online updates) — need segment tree or other dynamic structure
   • 2D grid version — reduce each column to a histogram problem, then apply this. Connects to LC 85 Maximal Rectangle

   Decision Point: Histogram rectangle = monotonic increasing stack. The sentinel trick (appending height 0 at the end) forces all remaining bars to be flushed from the stack at termination. Interviewer Comms: “I use a monotonic increasing stack of indices. When a shorter bar arrives, I pop taller bars — each popped bar’s rectangle extends from the new stack top to the current index. I append a sentinel bar of height 0 to flush everything at the end. Each bar enters and exits the stack once, so \(O(n)\) total.”

   Pitfalls and Misconceptions

   1. Trap: Computing width incorrectly when the stack is empty after a pop. Why: When the stack is empty, the popped bar’s rectangle extends all the way to the left edge (width = i, not i - stack[-1] - 1). Correction: width = i if not stack else i - stack[-1] - 1.
   2. Trap: Forgetting the sentinel value at the end. Why: Without the sentinel (a bar of height 0 at index n), bars remaining in the stack after the loop are never processed. Correction: Loop over range(len(heights) + 1) and use heights[i] if i < len(heights) else 0.
   3. Trap: Using a monotonically decreasing stack instead of increasing. Why: For finding boundaries of each bar as the minimum height, you need an increasing stack — shorter bars are boundaries, so you pop when you see a shorter bar. Correction: Maintain a stack where heights are non-decreasing.
   Problem Mutations

   1. What if the histogram were a 2D grid of 0s and 1s, and you needed the largest rectangle of all 1s? (stress-tests: 1D to 2D) Build a histogram per row (heights reset to 0 on a ‘0’, increment on a ‘1’), then apply LC 84 to each row’s histogram. Connects to LC 85 Maximal Rectangle.
   2. What if you needed the largest square instead of rectangle? (stress-tests: aspect ratio freedom) The side length is min(height, width). But the DP approach (dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1) is simpler for squares. Connects to LC 221 Maximal Square.
   3. What if bars could have negative heights? (stress-tests: non-negative assumption) “Largest rectangle” becomes ill-defined with negative heights. The monotonic stack approach assumes non-negative values.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Largest Rectangle in Histogram generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

3. 132 Pattern (456)

   We use the stack to keep “2"s / k s. For every j candidate as we go from right to left, we need to know where it’s min_left is (so we precompute this; these are the i s). Now we have a candidate for k, a candidate for min left and that for j, we just check if these candidates meet our rules.

   In relation to this canonical type, we are kind of finding out the next smaller element (dip) and then making greedy decisions there.

   For every j, we try to first cull it by making sure that it’s more than best i for that index (which we would have pre-processed). Then we check against the j value itself – either we find our ans or we accum it as a possible k value by pushing it to the stack

   Here’s more elaboration:

   1. Reframing the subsequence: we want 3 indices, left to right such taht:

      1. i: smallest, j: peak, k: drop
      2. k (the drop) can’t be smaller than i

   2. explore a brute-force framing

   3. Optimise the peak finding

      • if we can fix the peak (j) then at each peak, we could:

        1. try to know the smallest element to its left (which we call “min_left” for i < j)

        2. try to find a 2 to its right so that min_i < nums[k] < nums[j]

      • this means we have to precompute things properly (precompute min_i)

        • for values of “k” (2) we want to quickly be able to check if there’s any right-side value in the interval of min_i < nums[k] < nums[j] as we go from right to left.

      • using a stack:

        1. use it to find the “2"s.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Solution: def find132pattern(self, nums: List[int]) -> bool: n = len(nums) # trivial: if n < 3: return False # preproc: for each num, we need to know the value of the min number so far (inclusive) # these are our best possible i values. for both i and j, we min_left = [float('inf')] * n curr_min = nums[0] for i in range(len(nums)): curr_min = min(curr_min, nums[i]) min_left[i] = curr_min stack = [] # stack will have inconsideration values for what k could be. for j in range(n - 1, -1, -1): while stack and (not stack[-1] > min_left[j]): stack.pop() # clears out values that can't be k anymore # now all in the stack might be k or might be considered as a j if stack and stack[-1] < nums[j]: # we've found a k return True else: # now we can consider as a j for the next k candidate stack.append(nums[j]) return False

   Code Snippet 5: 132 Pattern (456)
   Pattern Extraction

   Core Insight: Sweep right-to-left maintaining a stack of potential “2” (k) candidates. The stack holds values greater than min_left[j]; if any are less than nums[j], we’ve found the 132 pattern. Pattern Name: Monotonic Stack with Precomputed Prefix State Canonical Section: Stack > Next Smaller/Greater Element Recognition Signals:

   • Three-element subsequence with a specific ordering relationship (not sorted — a “dip” pattern)
   • Need to track historical min/max to one side while scanning from the other
   • Two constraints to satisfy simultaneously: nums[i] < nums[k] < nums[j] with i < j > k

   Anti-Signals:

   • Looking for a sorted subsequence (increasing/decreasing) — different problem (LIS)
   • Only two elements — just two-pointer or hash map
   • Need all occurrences, not just existence — same approach but collect instead of early-return

   Decision Point: The “valley-peak-dip” shape (132 pattern) is the key. Precompute min_left for the “1”, scan right-to-left for the “3”, stack manages the “2”. The two-pass + stack combination is the canonical approach.

   Pitfalls and Misconceptions

   1. Trap: Scanning left-to-right and trying to maintain both “1” and “2” simultaneously. Why: Left-to-right, you don’t know the “3” (peak) yet, so you can’t evaluate the “2” against it. Right-to-left scanning lets you evaluate “2” candidates against known “3” (nums[j]) and “1” (min_left[j]). Correction: Precompute min_left (left-to-right), then scan right-to-left with the stack.
   2. Trap: Confusing which value is “1”, “2”, “3” — using nums[j] as the wrong role. Why: In the 132 pattern, “1” is smallest (nums[i]), “3” is peak (nums[j]), “2” is the dip after the peak (nums[k]). The stack holds “2” candidates, not “3” candidates. Correction: Map: 1 = min_left[j] (precomputed), 3 = nums[j] (current), 2 = stack values.
   Problem Mutations

   1. What if you needed to find a “123 pattern” (strictly increasing triplet subsequence)? (stress-tests: ordering shape) Much simpler — track the two smallest values seen so far. Connects to LC 334 Increasing Triplet Subsequence.
   2. What if you needed the count of all 132 patterns, not just existence? (stress-tests: boolean vs counting) The stack approach can be augmented to count: when popping “2” candidates, count how many valid triples each contributes. More complex bookkeeping required.
   3. What if you needed a “1324 pattern” (four elements)? (stress-tests: triplet to quadruplet) Significantly harder. Would need to track additional state or nest the pattern detection.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for 132 Pattern generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Maintaining Historical or Rolling State (Min/Max Stack) #

• Key idea: You need to efficiently maintain and retrieve some aggregate value (minimum/maximum) among elements seen so far.

• Pattern: Keep the current value plus auxiliary info of min/max in stack elements.

• Reasoning: Stack tracks state cumulatively, enabling O(1) queries. It’s the cumulative rolling state that is literally our history.

Problems #

1. Min Stack (155) (stack with \(O(1)\) min retrieval)

   Here we can just keep track of previous min known, so we can keep tuples in our stack and when required just get it in \(O(1)\) time. Straight up plain history tracking here.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class MinStack: def __init__(self): self.stack = [] # holds (val, min_so_far) def push(self, val: int) -> None: min_so_far = val if not self.stack else min(val, self.stack[-1][1]) self.stack.append((val, min_so_far)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]

   Code Snippet 6: Min Stack (155)
   Pattern Extraction

   Core Insight: Pair each value with the running minimum at the time it was pushed; since the stack is LIFO, popping restores the previous minimum without recomputation. Pattern Name: Augmented Stack with Rolling State Canonical Section: Stack > Maintaining Historical or Rolling State Recognition Signals:

   • Stack with \(O(1)\) retrieval of some aggregate (min, max, sum)
   • The aggregate changes with push/pop operations
   • Each element’s contribution to the aggregate depends only on prior elements (LIFO property)

   Anti-Signals:

   • Need \(O(1)\) access to arbitrary positions — stack doesn’t support random access
   • Need to pop the minimum element itself, not just query it — that’s a priority queue / “max stack” problem. Connects to LC 716 Max Stack

   Decision Point: “Get min in \(O(1)\)” = augmented stack. “Pop min in \(O(1)\)” = priority queue or sorted structure.

   Pitfalls and Misconceptions

   1. Trap: Maintaining a separate variable for the global minimum without history. Why: When you pop the current minimum, you can’t recover the previous minimum without scanning the stack. Correction: Store (value, min_so_far) tuples so each pop restores the previous min.
   2. Trap: Using a separate min-stack that tracks minimum values — pushing the min onto a second stack. Why: Works (two-stack approach) but uses more space. The tuple approach is simpler and equivalent. Correction: Either approach is valid. Tuples are cleaner; two stacks are sometimes easier to reason about.
   Problem Mutations

   1. What if you needed \(O(1)\) max retrieval as well? (stress-tests: single aggregate) Store (value, min_so_far, max_so_far) triples. Same logic, one more field per entry.
   2. What if you needed to pop the minimum element (not the top)? (stress-tests: LIFO pop assumption) This is a fundamentally different data structure — a min-heap + stack hybrid. Connects to LC 716 Max Stack which uses a doubly-linked list + sorted map.
   3. What if the stack supported increment operations on the bottom \(k\) elements? (stress-tests: top-only access) Use lazy increment tracking with a difference-array-like approach. Connects to LC 1381 Design a Stack With Increment Operation.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Min Stack generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Segment & Range Partitioning Problems #

• Key idea: Divide data into consecutive segments based on dynamic boundaries identified from stack.

• Pattern: Stack helps identify partitions or buckets where conditions hold. There’s some overlap between this usage and the next greater / next smaller element style usage of stacks.

• Reasoning: Stack encodes boundaries and/or possible merges (the actual answer).

Problems #

1. Largest Rectangle in Histogram (84) ⭐️ see this

2. Trapping Rainwater (42) (the monotonic stack variant) ⭐️

   The monotonic stack variant is a sub-optimal in its use of space but a valid, working approach. The optimal approach being a 2 pointer approach.

   Stack keeps indices of bar heights that haven’t found a taller bar to the right (not right bounded), once found, all the walls in the stack can use this right wall as their right boundary and we can get their respective valley depth. We just accumulate thereafter.

   Actually this question also has other approaches we can consider as well, typically all of the following approaches should work well:

   1. converging pointers solution – optimal, \(O(n)\) time, \(O(1)\) space [ For the 2-pointer approach: ]

      We ask ourselves how water gets trapped and we realise that we need to find valleys. So we need to keep track of a max left and max right (heights) for each index we see because the amount of water trapped depends on the best height to the right and the best height to the left \(\implies\) how deep the valley is. This is the key guiding characteristic for this question.

      This gives us the greedy observation that we should shift the limiting pointer (the one that is shorter of the two [right, left])

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

      # M1: converging pointers solution (optimal) O(n) time, O(1) space class Solution: def trap(self, height: List[int]) -> int: if not height: return left, right = 0, len(height) - 1 max_left, max_right = height[left], height[right] accum = 0 while left < right: # if left is shorter, then instead of the right boundary, this is the one that is limiting it if is_left_shorter:=(max_left < max_right): left += 1 # we compare the immediate next to the limited boundary: max_left = max(max_left, height[left]) valley_depth = max_left - height[left] accum += max(valley_depth, 0) else: # mirror right -= 1 # compare the immediate max_right = max(max_right, height[right]) valley_depth = max_right - height[right] accum += max(valley_depth, 0) return accum

      Code Snippet 7: Trapping Rainwater (42) (the monotonic stack variant)

   2. stack based approach – suboptimal in space usage: \(O(n)\) time, \(O(n)\) space We use stack to keep track of all the “next greater than"s

      • stack keeps indices of bar heights that haven’t found a taller bar to the right
      • when encountering a bar taller than the bar at the idx stored at the top of the stack ==> we can trap water above the bar represented by that index

        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

        # M2: Stack based approach O(n) time, O(n) space class Solution: def trap(self, height): if not height: return 0 n = len(height) trapped_water = 0 stack = [] for i in range(n): # While there are indices in stack and current height is # greater than height at index stored on top of stack while stack and height[i] > height[stack[-1]]: top = stack.pop() # Get index of top element if not stack: # If stack is empty after popping break # Calculate width width = i - stack[-1] - 1 # Calculate bounded height bounded_height = min(height[i], height[stack[-1]]) - height[top] # Update total trapped water trapped_water += width * bounded_height # Push current index onto stack stack.append(i) return trapped_water

   3. prefix-sum approach: \(O(n)\) time \(O(n)\) space this is like the converging pointers solution but without the O(1) space optimisation.

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

      # M3: Prefix Sum approach O(n) time, O(n) space class Solution: def trap(self, height: List[int]) -> int: if not height: return n = len(height) left_maxes, right_maxes = [0] * n, [0] * n for i in range(n): prev_max = left_maxes[i - 1] if i - 1 >= 0 else 0 left_maxes[i] = max(prev_max, height[i]) # right maxes, we accumulate from right to left for i in range(n - 1, - 1, -1): next_max = right_maxes[i + 1] if i + 1 < n else 0 right_maxes[i] = max(next_max, height[i]) accum = 0 for idx, (left_max, right_max) in enumerate(zip(left_maxes, right_maxes)): valley_height = height[idx] limiting = min(left_max, right_max) accum += limiting - valley_height return accum

3. Car Fleet (853)

   Merging from one-side problem. Can view the problem as creating contiguous segments of the cars array based on arrival times after merging. Each segment maps to exactly one car fleet. Top of the stack will be the next arriving fleet, nearest to the destination, we have to just check if the car in consideration is going to be part of that fleet or will start a new fleet.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: cars = sorted(list(zip(position, speed)), reverse=True) arrival_time_stack = [] for pos, s in cars: arrival_time = (target - pos) / s if not arrival_time_stack: # empty stack arrival_time_stack.append(arrival_time) continue # if slower than the prev arrival, then it's a new fleet, else ignore this: if arrival_time_stack and arrival_time > arrival_time_stack[-1]: arrival_time_stack.append(arrival_time) return len(arrival_time_stack)

   Code Snippet 8: Car Fleet (853)

   for completeness, here’s a heap-based approach that is similar

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   import heapq from typing import List class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: # Build max-heap based on position (negate to simulate max-heap with Python's min-heap) heap = [(-pos, speed[i]) for i, pos in enumerate(position)] heapq.heapify(heap) fleets = 0 last_arrival_time = 0.0 # Process cars from closest to target (largest position) to farthest while heap: pos, spd = heapq.heappop(heap) pos = -pos # revert negation to original position arrival_time = (target - pos) / spd # If current car's arrival time is greater than last fleet's time, it forms a new fleet if arrival_time > last_arrival_time: fleets += 1 last_arrival_time = arrival_time # else, it merges into the fleet represented by last_arrival_time return fleets

   Code Snippet 9: Car Fleet (853)
   Pattern Extraction

   Core Insight: Sort cars by starting position (farthest first). A slower car ahead blocks all faster cars behind it — they merge into a fleet. The stack holds arrival times; if a car behind arrives at or before the car ahead, it merges (pop); otherwise it’s a new fleet. Pattern Name: Monotonic Stack on Computed Properties (arrival time merging) Canonical Section: Stack > Monotonic Stack Applications Recognition Signals:

   • Objects with position and speed moving toward a target
   • Collisions/merging when a faster object catches a slower one
   • Need to count groups after all merges
   • Processing order matters (sort by position)

   Anti-Signals:

   • Objects can pass through each other — no merging, just simulation
   • Need the exact collision time/position — more detailed simulation required
   • Multiple dimensions — 1D merging doesn’t generalise easily

   Decision Point: Sort by position descending, compute arrival times, then use a stack to merge fleets. The stack holds the “effective arrival times” of fleet leaders.

   Pitfalls and Misconceptions

   1. Trap: Sorting by position ascending instead of descending. Why: We need to process cars from the one closest to the target backwards. A car can only be blocked by one ahead of it (closer to target), so process front-to-back. Correction: Sort zip(position, speed) and iterate in reverse, or sort descending by position.
   2. Trap: Using integer division for arrival time instead of float. Why: (target - pos) // speed loses precision. Cars with fractionally different arrival times are separate fleets. Correction: Use (target - pos) / speed (float division).
   3. Trap: Forgetting that a car EXACTLY at the target still counts as a fleet. Why: A car with position equal to target has arrival time 0 and is its own fleet. Correction: Include it normally; the algorithm handles it.
   Problem Mutations

   1. What if cars could decelerate upon merging? (stress-tests: constant speed assumption) The arrival-time comparison breaks because merged fleet speed changes. Would need simulation with event-driven processing.
   2. What if we needed the number of fleets at a specific time \(t\), not at arrival? (stress-tests: final state) Compute positions at time \(t\), then check which cars have caught their fleet leader by then. More complex threshold logic.
   3. What if there were multiple lanes and cars could change lanes? (stress-tests: single lane) Fundamentally different problem — need to model lane-changing decisions, likely simulation or DP.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Car Fleet generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

4. Remove duplicate letters (316) (tracking lex order) We have to do some preprocessing so that we know the last_position of each char. This is because we can only choose to discard a char if it’s a duplicate and this current char we’re considering is NOT the last possible position.

   We accumulate the result in the stack. Ideally the top of the stack should be the lexigraphically highest (in that region). We can discard it if:

   1. that element appears again later to the right (requires some pre-processing before main routine), and
   2. if the top of stack element is lexicographically bigger than the curr char.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   class Solution: def removeDuplicateLetters(self, s: str) -> str: # pre-processing: keeps the last position of a duplicate, if found. This allows us to reject charaters easier last_pos = {} for idx, char in reversed(list(enumerate(s))): if char not in last_pos: last_pos[char] = idx stack = [] # use this to build the res visited = set() for idx, c in enumerate(s): if not stack: stack.append(c) visited.add(c) continue if c in visited: continue # as long as top of stack can be discarded: # A: it is lexically bigger than C AND (reject because we want lexically smallest result) # B: it comes later while(stack and stack[-1] > c and idx < last_pos[stack[-1]]): visited.remove(stack.pop()) stack.append(c) visited.add(c) return "".join(stack)

   Code Snippet 10: Remove duplicate letters (316)
   Pattern Extraction

   Core Insight: Build the lexicographically smallest subsequence containing each character exactly once using a greedy monotonic stack: pop a character if a smaller one arrives AND the popped character appears later in the string. Pattern Name: Greedy Monotonic Stack with Future-Availability Check Canonical Section: Stack > Monotonic Stack Applications Recognition Signals:

   • “Lexicographically smallest” result containing specific characters
   • Each character must appear exactly once
   • Greedy character-by-character construction with lookahead
   • Need to know future availability of characters (last occurrence tracking)

   Anti-Signals:

   • Can use all occurrences (not “exactly once”) — simpler problem
   • Need to preserve original order strictly — can’t do the stack-based reordering

   Decision Point: “Lexicographically smallest” + “each character exactly once” + “preserving relative order” = greedy monotonic stack with last-occurrence tracking.

   Pitfalls and Misconceptions

   1. Trap: Popping a character from the stack when it has no future occurrences. Why: If you pop a character that doesn’t appear later, you’ve lost it forever. The result will be missing that character. Correction: Only pop stack[-1] if its last occurrence is after the current index: last[stack[-1]] > i.
   2. Trap: Adding a character that’s already in the stack. Why: Including it again would violate “each character exactly once.” Use a seen set. Correction: Skip characters already in the seen set.
   Problem Mutations

   1. What if you needed the lexicographically LARGEST instead of smallest? (stress-tests: comparison direction) Flip the comparison: pop when stack[-1] < c (ascending stack instead of descending). Everything else is the same.
   2. What if you needed to keep at most \(k\) characters? (stress-tests: keep-all-unique constraint) Track a length budget. Pop eagerly when the stack is full and a better character arrives, but only if enough characters remain.
   3. What if characters could appear at most \(k\) times instead of exactly once? (stress-tests: uniqueness constraint) Need a counter-based tracking instead of a boolean seen set. The greedy logic generalises but bookkeeping is more complex.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Remove Duplicate Letters generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Specialized Queues Using Stack-like Patterns (Monotonic Queues) #

• Key idea: Extends monotonic stacks with sliding window logic to maintain max/min over a window.
• Reasoning: Efficiently manages candidates using stack-like push/pop for window dynamics.

Problems #

1. Sliding Window Maximum (239) ⭐️ (monotonic queue implemented with deque)

   We’re being asked for max values within fixed-size sliding windows as we move the sliding window from left to right. The first thing that comes to mind is the nature of a single sweep monotonic stack approach. Except in this case, we don’t need a FILO approach, we can just keep it FIFO. So it’s a queue that we need to use.

   So our key intuition is: consider an entry and exit into the window. On entry, if new entry is bigger than the max in current window, then we can just pop everything within the current window since it’s not going to be useful to us (useful pruning).

   Also what to store? We should just store the indices so that we can do width calculations easily.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # keeping indices here, this is a monotonically decreasing queue, so left to right is largest to smallest valued-indices dq = deque() res = [] for idx, num in enumerate(nums): # remove those outside the window, it iterates "left to right" if dq and dq[0] <= (idx - k): dq.popleft() # since num comes into the window, # if it's the max value, then the ones less than num are irrelevant, we remove them while dq and nums[dq[-1]] < num: dq.pop() # add current idx (for the current num) into window. dq.append(idx) # at least it's the correct window size: if (idx >= k - 1): res.append(nums[dq[0]]) return res

   Code Snippet 11: Sliding Window Maximum (239)
   Pattern Extraction

   Core Insight: A monotonic decreasing deque maintains candidates for the window maximum: the front is always the current max, and elements that can never be the max (smaller and older) are eagerly removed from the back. Pattern Name: Monotonic Deque for Sliding Window Extremes Canonical Section: Stack > Monotonic Deque (Queue-based Stack variant) Recognition Signals:

   • Fixed-size sliding window + max/min query per window position
   • Need \(O(n)\) total (amortised \(O(1)\) per window position)
   • Deque supports removal from both ends (back for monotonicity, front for window expiry)

   Anti-Signals:

   • Variable-size window — still works but window expiry logic changes
   • Need median, not max/min — use two heaps or sorted set, not a deque
   • Need sum or average — use prefix sums, not a deque

   Decision Point: Window max/min = monotonic deque. Window sum/average = prefix sums. Window median = two heaps or sorted set. Interviewer Comms: “I use a deque storing indices in decreasing order of value. For each new element: (1) expire indices outside the window from the front, (2) pop indices from the back whose values are <= current (they’ll never be the max), (3) push the current index. The front of the deque is always the current window max. Amortised \(O(1)\) per element, \(O(n)\) total.”

   Pitfalls and Misconceptions

   1. Trap: Using a max-heap instead of a monotonic deque. Why: A heap can’t efficiently remove expired elements from the middle. Lazy deletion works but adds complexity and worst-case overhead. Correction: Use a deque — it supports \(O(1)\) removal from both ends, which is exactly what the window max problem needs.

      1. Trap: Storing values in the deque instead of indices.

      Why: You need indices to check window expiry (deque[0] < i - k + 1). Values alone don’t tell you if an element has left the window. Correction: Store indices; access values via nums[deque[0]].

      1. Trap: Removing from the wrong end — confusing front and back operations.

      Why: Expired elements leave from the front (FIFO); dominated elements leave from the back (LIFO). Mixing these up breaks both the monotonicity invariant and window bounds. Correction: Front popleft() for expiry; back pop() for monotonicity.

   Problem Mutations

   1. What if you needed sliding window MINIMUM instead of maximum? (stress-tests: comparison direction) Flip to a monotonic increasing deque: pop from back when current < back. Everything else identical.

      1. What if the window size varied per position? (stress-tests: fixed window)

      Expiry check becomes position-dependent. The deque approach still works but the expiry condition changes.

      1. What if you needed the sliding window median? (stress-tests: extreme vs central statistic)

      Deque doesn’t work for median. Use two heaps (max-heap for lower half, min-heap for upper half) with lazy deletion. Connects to LC 480 Sliding Window Median.

      1. What if elements were being inserted and deleted at arbitrary positions? (stress-tests: sequential processing)

      Need a balanced BST or order-statistic tree for \(O(\log n)\) max queries with arbitrary updates.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Sliding Window Maximum generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. TODO Maximum and Minimum Sums of at Most Size K Subarrays (3430) ⭐️ ⭐️

   Since we use subarrays, our mind immediately picks up on the contiguous part:

   1. a sliding window approach might work

      • here’s one: ref

   2. alternative counting approach might work – contribution counting

      • here we consider each element and that may be a pivot point (either max or min for a subarray)
      • we need to count how many subarrays that it’s a part of
      • so need to pre-process the prev and next smaller and greater values (4 pre-processed info). That’s what a monotonic stack can be used for.
   counting approach with monotonic stack

   This problem is about contribution counting: for every i th element, how many subarrays is it part of for which it is the min, how many subarrays is it part of for which it is the max.

   Each element contributes to many subarrays, not just the ones that start at idx.

   Follows the trend where we find complementary approaches to framing the problem.

   Key Idea: we need to rephrase our approach to the question, think in complements.

   • THINK: “For each element, count how many subarrays it is the min(and max) of”
   • DO NOT THINK: “For each subarray, compute min + max”

   solution:

Auxiliary Use #

TODO Stack used to manage active intervals #

In cases like windowing questions or interval merging or skyline profile problems, we can use a stack to track active intervals.

Graph DFS / Topo Sorting Algos #

These use stacks implicitly.

SOE #

1. Off by one errors implicitly done \(\implies\) remember to allow every option to be considered (e.g. to be inserted into monotonic stack if it makes sense). This might require us to add in some dummy values / use some sentinel values for things to make sense.

   the largest rectangle question is a good example of this

       ## M1: USE A SENTINEL BAR (in the context of the question)
       class Solution:
           def largestRectangleArea(self, heights: List[int]) -> int:
               # we store indices and make decisions on the bars in this stack
               stack = []
               max_area = 0
               for i in range(len(heights) + 1): # ensures that the last bar is added to the stack
                 curr_height = heights[i] if i < len(heights) else 0 # Sentinel bar: pops all at the end
                 # the bar in consideration is always the bar at the top of the stack
                 while (found_right_boundary:= stack and curr_height < heights[stack[-1]]):
                   min_height = heights[stack.pop()]
                   # empty stack: either i = 0 or the inputs are such that it's a consistently declining slope so far
                   width = i if not stack else i - stack[-1] - 1
                   max_area = max(max_area, min_height * width)
   
                 # add the small left boundary
                 stack.append(i)
   
               return max_area
   
       # M2: USE A SENTINEL VALUE
       class Solution:
           def largestRectangleArea(self, heights: List[int]) -> int:
               stack = [-1]
               max_area = 0
               for i, h in enumerate(heights):
                   while stack[-1] != -1 and heights[stack[-1]] >= h:
                       height = heights[stack.pop()]
                       width = i - stack[-1] - 1
                       max_area = max(max_area, height * width)
                   stack.append(i)
               n = len(heights)
               while stack[-1] != -1:
                   height = heights[stack.pop()]
                   width = n - stack[-1] - 1
                   max_area = max(max_area, height * width)
               return max_area

   Code Snippet 12: Graph DFS / Topo Sorting Algos

2. kind of related SOE as 1 is not handling the expected sentinel value / object properly. If we’re keeping in-consideration elements within the stack — then we might agree that for all elements to be considered, they must at least be in the stack once. This means the last element needs to be in the stack as well. If the real-world context of the question limits this then we should be using a sentinel value.

   this is an elegant way of handling things typically. Alternatively, we could just add one more manual check to make sure that the stack is empty towards the end.

3. Forgetting to pop after handling the condition – leaving stale elements in the stack that corrupt subsequent computations.

4. Wrong handling of empty stack

5. GENERIC MATH GOTCHA: division “truncates towards zero”

   One pitfall is in not realising the division is described to be “tend to zero” instead of “tend to infinity” In Python, / does floor division, which always rounds towards negative infinity. The problem statement for Evaluate Reverse Polish Notation (LeetCode 150) specifies that division between two integers should truncate towards zero, not negative infinity. For example, =-7 / 2 = -4, but the answer should be -3.

   We can do this instead: '/': lambda a, b: int(a / b) # IMPORTANT:truncates towards zero

Decision Flow #

1. Nested structure / hierarchy management / matching of pairs? → Stack

2. boundary finding, Next greater/smaller element? → Monotonic stack, the stack will contain the currently unresolved elements

3. History-tracking / Track state cumulatively, for the purpose of doing some querying then we can use stack for aux info tracking \(\rightarrow\) use a stack for the stats tracking

4. something about min / max on subarrays (continguous) then consider using monotonic stack (or sliding window approaches maybe).

Drawing similarities between backtracking and stack based solutions #

In questions like “Generate Parentheses” I think it’s intuitive to think of the recursive solution, which makes sense because it’s a combinations questions and backtracking helps us to the brute-force approach to finding combinations:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def backtrack(curr, open_count, close_count):
            if len(curr) == 2 * n:
                res.append(curr)
                return
            if open_count < n:
                backtrack(curr + "(", open_count + 1, close_count)
            if close_count < open_count:
                backtrack(curr + ")", open_count, close_count + 1)

        backtrack("", 0, 0)
        return res

Here, realise that the recursive stack is our stack. So we could write it iteratively like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        TOTAL = n * 2
        stack = [("", 0, 0)]  # Each element: (current_string, num_open, num_close)

        while stack:
            path, num_open, num_close = stack.pop()

            if len(path) == TOTAL:
                res.append(path)
                continue

            # If we can add a closing parenthesis
            if num_close < num_open:
                stack.append((path + ")", num_open, num_close + 1))

            # If we can add an opening parenthesis
            if num_open < n:
                stack.append((path + "(", num_open + 1, num_close))

        return res

this is similar to how we do state-tracked BFS approaches when we explore trees, wherein the accumulative state we just put it within as well.

Styles, Tricks and Boilerplate #

Recipes #

• Math Recipe: “Division Tend to Zero” \(\implies\) use int(7/2) to truncate to nearest integer instead of 7 // 2

Python #

• generate cartesian product:
  • this creates cartesian product: info = sorted([(p, s) for s in speed for p in position])
• use zip on the inputs to create pairs: info = sorted(zip(position, speed)
• python set remove vs discard :
  • remove will throw an error if that element is not present in the set
  • discard will not throw an error if not present

Tricks #

• time can be the common dimension in things like speed-based or location based questions.

  For speed, distance questions, it’s good to realise that time can be the common dimension instead of having to consider speed, location separately we can just combine them into time.

• Backtracking boilerplate: because of the earlier point about how there’s a common thread between solving problems via backtracking (recursive framing) and solving it using a monotonic stack (iterative framing). The comments here show the first few things to think about when implementing the backtrack:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] TOTAL = n * 2 def backtrack(path, num_open, num_close): # end states: if len(path) == TOTAL: res.append(path) return # choice type 1: if should_add_closer:=(num_close < num_open): backtrack(path + ")", num_open, num_close + 1) # choice type 2: if should_add_opener:=(num_open < n): backtrack(path + "(", num_open + 1, num_close) return backtrack("", 0, 0) return res

  Code Snippet 15: Recipes

  see Backtracking topic for more info.

• Mental visualisation / representing diagrams:

  When drawing out a stack, draw it horizontally. This allows you to visualise both the LIFO behaviour as well as the fact that it’s just a list.

TODO KIV #

[ ] Calculator Family of Problems #

because the basic RPN isn’t sufficient, there’s the ambiguity handling that is important

Online Stock Span (901) #

Max Stack (716) and its variants #

• it’s a paid question, but we can find info about it on algomonster. basically we need to have FILO behaviour along with the ability to pop from anywhere \(\implies\) we can consider using a deque for things that stores referenes to nodes within the stack.

Maximum and Minimum Sums of at Most Size K Subarrays (3430) #

More canonicals to explore #

1. Undo/Redo Problems

   • Many editor/design/app-related problems require simulating undo/redo functionality using two stacks for state rollback/forward.

   • Example: Design Browser History (Leetcode 1472).

2. Infix to Postfix/Prefix Conversion & Expression Parsing

   • Use stacks for parsing arithmetic expressions, operator precedence, and evaluation.

   • Example: Basic Calculator (Leetcode 224, 227, 772).

3. Backspace String Compare

   • Simulate a text editor with backspaces—stack records typed characters and pops on backspaces.

   • Example: Backspace String Compare (Leetcode 844).

4. Decode/Encode Nested Strings

   • Handle nested and repeated string patterns, keeping state for repeats and substrings.

   • Example: Decode String (Leetcode 394).

5. Tree Traversal (Iterative)

   • Simulate recursion with explicit stacks for preorder, inorder, or postorder traversals.

   • Example: Binary Tree Inorder Traversal (Leetcode 94), Postorder (145).

6. Path Simplification Problems

   • Canonical for stack-based simplification of Unix file system paths.

   • Example: Simplify Path (Leetcode 71).

7. Balanced/Valid String Formation

   • Stack maintains state to check if string formation (including wildcard cases) is valid.

   • Example: Valid Parenthesis String (Leetcode 678).

8. Plate/Stack Design Patterns

   • Where a real-life stack-of-stacks or set-of-stacks is required.

   • Example: Dinner Plate Stacks (Leetcode 1172).