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 #

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 = list(openerToCloser.keys())
       closers = list(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

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.

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.
Pattern:
- Maintain a monotonically increasing or decreasing stack of indices or elements.
- Pop from stack when current (in-consideration as the greater than for some other index) element breaks the monotonic property.
- Reasoning:
  The stack holds unresolved candidates in order so boundaries are efficiently found.

Problems #

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

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.

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

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 #

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 = []

        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 #

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

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

Remove duplicate letters (316) (tracking lex order)

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 a) that element appears again later to the right (requires some pre-processing before main routine), and b) 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
30
31
    from collections import Counter

    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 #

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

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

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 #

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

kind of related is not handling the expected sentinel value / object properly
Forget to pop after handling condition
Wrong handling of empty stack
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 #

Nested structure / matching? → Stack
Next greater/smaller element? → Monotonic stack

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 #

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])
- this creates pairs: info = sorted(zip(position, speed)
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:

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

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 #

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).
Infix to Postfix/Prefix Conversion & Expression Parsing
- Use stacks for parsing arithmetic expressions, operator precedence, and evaluation.
- Example: Basic Calculator (Leetcode 224, 227, 772).
Backspace String Compare
- Simulate a text editor with backspaces—stack records typed characters and pops on backspaces.
- Example: Backspace String Compare (Leetcode 844).
Decode/Encode Nested Strings
- Handle nested and repeated string patterns, keeping state for repeats and substrings.
- Example: Decode String (Leetcode 394).
Tree Traversal (Iterative)
- Simulate recursion with explicit stacks for preorder, inorder, or postorder traversals.
- Example: Binary Tree Inorder Traversal (Leetcode 94), Postorder (145).
Path Simplification Problems
- Canonical for stack-based simplification of Unix file system paths.
- Example: Simplify Path (Leetcode 71).
Balanced/Valid String Formation
- Stack maintains state to check if string formation (including wildcard cases) is valid.
- Example: Valid Parenthesis String (Leetcode 678).
Plate/Stack Design Patterns
- Where a real-life stack-of-stacks or set-of-stacks is required.
- Example: Dinner Plate Stacks (Leetcode 1172).