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

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]

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

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

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]

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) ⭐️

   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. We are actually searching for contiguous ranges here.

   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.

   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

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

   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)

   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

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)

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

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

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. Forget to pop after handling conditi

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, Recipes, 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

  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).