Chapter 7a — Stack & Queue Problem Patterns

Every problem here has a brute force that re-checks old information. The stack/queue eliminates that re-checking.

Pattern Map

Problem 1: Valid Parentheses

Problem: Given a string of ()[]{}, determine if it is valid. Every open bracket must close in the correct order.
isValid("()[]{}") → true
isValid("([)]") → false
LeetCode 20. Most fundamental stack problem. Every company.

Four Questions

Q1: What do I have? A string containing only (, ), [, ], {, }.
Q2: What do I want? True if every open bracket has a matching close bracket in the correct order.
Q3: What is the brute force? Repeatedly scan and remove matched pairs like () until no changes or the string is empty. O(n²).
Q4: Where is the waste? Re-scanning. The inner-most unmatched open bracket is always the one we care about — exactly the top of the stack.

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') {
      stack.push(c);          // open bracket: push
    } else {
      // close bracket: top of stack must match
      if (stack.length === 0 || stack[stack.length - 1] !== pairs[c]) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;  // all opens were matched
}

Dry Run: isValid("({[]})")

c='(' open → stack=['('].
c='{' open → stack=['(','{'].
c='[' open → stack=['(','{','['].
c=']' close → pairs[']']='['. stack.top='['. Match! pop. stack=['(','{'].
c='}' close → pairs['}']={. stack.top='{'. Match! pop. stack=['('].
c=')' close → pairs[')']='('. stack.top='('. Match! pop. stack=[].

stack.length===0 → return true. ✓

Dry Run: isValid("([)]")

c='(' → stack=['('].
c='[' → stack=['(','['].
c=')' → pairs[')']='('. stack.top='['. '(' ≠ '[' → return false. ✓

Edge cases:

• Empty string: stack stays empty → return true. ✓
• "]" alone: stack is empty when we see ] → stack.length === 0 → return false. ✓
• "(((" all opens: stack = ['(','(','('] at end, not empty → return false. ✓

Complexity: O(n) time, O(n) space (stack holds at most n/2 open brackets).

Interview signal: Any problem with nested matching — XML/HTML tag matching, bracket checking in code editors, JSON validation — is this pattern.

Problem 2: Min Stack

Problem: Implement a stack with push, pop, top, and getMin, all O(1).
LeetCode 155. Amazon, Google, Bloomberg.

Fully built in Chapter 7. Here's the clean implementation with the key insight restated:

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(val) {
    this.stack.push(val);
    const prevMin = this.minStack.length > 0
      ? this.minStack[this.minStack.length - 1]
      : Infinity;
    this.minStack.push(Math.min(val, prevMin));
  }

  pop() {
    this.stack.pop();
    this.minStack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

Dry Run

push(5):  stack=[5],   minStack=[5].
push(3):  stack=[5,3], minStack=[5,3].
push(7):  stack=[5,3,7], minStack=[5,3,3]. ← min is still 3
getMin(): return 3. ✓
pop():    stack=[5,3], minStack=[5,3].
getMin(): return 3. ✓
pop():    stack=[5], minStack=[5].
getMin(): return 5. ✓

The key insight: minStack[i] answers "what is the minimum among all elements at index 0 through i?" Popping from both stacks simultaneously maintains this invariant.

Problem 3: Evaluate Reverse Polish Notation

Problem: Evaluate an arithmetic expression in Reverse Polish Notation (postfix).
Tokens are integers or +, -, *, /.
evalRPN(["2","1","+","3","*"]) → 9 (equivalent to (2+1)*3)
LeetCode 150.

Why RPN Doesn't Need Parentheses

In RPN, operators come after their operands. When you see an operator, you know the two most recent operands are its arguments — the stack gives them to you directly. No precedence parsing needed.

Four Questions

Q1: What do I have? Array of string tokens in postfix order.
Q2: What do I want? The integer result of evaluating the expression.
Q3: What is the brute force? Repeatedly scan for operators between two numbers, reduce. O(n²).
Q4: Where is the waste? Re-scanning. When you see an operator, the two most recent operands are exactly what you need — top two of the stack.

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (token === '+' || token === '-' || token === '*' || token === '/') {
      const b = stack.pop();  // second operand (arrived later)
      const a = stack.pop();  // first operand (arrived earlier)
      if (token === '+') stack.push(a + b);
      else if (token === '-') stack.push(a - b);
      else if (token === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));  // truncate toward zero
    } else {
      stack.push(Number(token));  // operand: push
    }
  }

  return stack[0];
}

Dry Run: evalRPN(["2","1","+","3","*"])

token="2": stack=[2].
token="1": stack=[2,1].
token="+": b=1, a=2. push(2+1=3). stack=[3].
token="3": stack=[3,3].
token="*": b=3, a=3. push(3*3=9). stack=[9].

return 9. ✓

Dry Run: evalRPN(["4","13","5","/","+"]) (= 4 + (13/5) = 4 + 2 = 6)

token="4": stack=[4].
token="13": stack=[4,13].
token="5": stack=[4,13,5].
token="/": b=5, a=13. Math.trunc(13/5)=2. stack=[4,2].
token="+": b=2, a=4. push(6). stack=[6].
return 6. ✓

Why pop b first then a? The stack is LIFO. The second operand (b) was pushed last, so it's on top. For subtraction and division order matters: a - b and a / b where a is the first/left operand. Always pop right operand first.

Complexity: O(n) time, O(n) space.

Problem 4: Daily Temperatures

Problem: Given an array of daily temperatures, return an array where result[i] is the number of days until a warmer temperature. If no warmer day, return 0.
dailyTemperatures([73,74,75,71,69,72,76,73]) → [1,1,4,2,1,1,0,0]
LeetCode 739. Most asked monotonic stack problem.

Four Questions

Q1: What do I have? Array of temperatures. temps[i] is temperature on day i.
Q2: What do I want? For each day i, find the smallest j > i where temps[j] > temps[i]. Return j - i (or 0 if none).
Q3: What is the brute force? For each day, scan right until you find a warmer day. O(n²).
Q4: Where is the waste? If day 0 (73°) hasn't found its warmer day yet, and day 1 (74°) arrives — 74 > 73, so day 0's answer is day 1 (distance 1). The stack holds indices of days "still waiting for a warmer day." When a warmer day arrives, resolve all waiting days it satisfies.

function dailyTemperatures(temps) {
  const result = new Array(temps.length).fill(0);
  const stack = [];  // indices of days waiting for a warmer day

  for (let i = 0; i < temps.length; i++) {
    // Pop all days cooler than today — today is their warmer day
    while (stack.length > 0 && temps[stack[stack.length - 1]] < temps[i]) {
      const prevDay = stack.pop();
      result[prevDay] = i - prevDay;
    }
    stack.push(i);
  }

  // Remaining in stack: no warmer day → result stays 0
  return result;
}

Full Dry Run: dailyTemperatures([73,74,75,71,69,72,76,73])

result=[0,0,0,0,0,0,0,0]. stack=[].

i=0, temp=73:
  stack empty. Push 0. stack=[0]. (day 0 waiting)

i=1, temp=74:
  temps[0]=73 < 74. Pop 0. result[0]=1-0=1.  ← day 0 waits 1 day ✓
  stack=[]. Push 1. stack=[1].

i=2, temp=75:
  temps[1]=74 < 75. Pop 1. result[1]=2-1=1.  ← day 1 waits 1 day ✓
  stack=[]. Push 2. stack=[2].

i=3, temp=71:
  temps[2]=75 > 71. Don't pop.
  Push 3. stack=[2,3].

i=4, temp=69:
  temps[3]=71 > 69. Don't pop.
  Push 4. stack=[2,3,4].

i=5, temp=72:
  temps[4]=69 < 72. Pop 4. result[4]=5-4=1.  ← day 4 waits 1 day ✓
  temps[3]=71 < 72. Pop 3. result[3]=5-3=2.  ← day 3 waits 2 days ✓
  temps[2]=75 > 72. Stop.
  Push 5. stack=[2,5].

i=6, temp=76:
  temps[5]=72 < 76. Pop 5. result[5]=6-5=1.  ← day 5 waits 1 day ✓
  temps[2]=75 < 76. Pop 2. result[2]=6-2=4.  ← day 2 waits 4 days ✓
  stack=[]. Push 6. stack=[6].

i=7, temp=73:
  temps[6]=76 > 73. Don't pop.
  Push 7. stack=[6,7].

End. stack=[6,7] → result[6]=0, result[7]=0. ✓

result=[1,1,4,2,1,1,0,0] ✓

Stack state at each step: the stack always maintains indices in decreasing order of temperature (largest at bottom, smallest at top). This is the monotonic decreasing invariant.

Complexity: O(n) time — each index pushed once, popped at most once. O(n) space.

Problem 5: Next Greater Element II (Circular Array)

Problem: Given a circular array, find the next greater element for each element. In circular, after the last element comes the first.
nextGreaterElements([1,2,1]) → [2,-1,2]
LeetCode 503.

The Circular Trick

For a non-circular array, one left-to-right pass suffices. For circular, we need to "wrap around." The trick: process the array twice (indices 0 to 2n-1, modulo n).

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];  // indices

  for (let i = 0; i < 2 * n; i++) {
    const idx = i % n;  // circular index

    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[idx]) {
      result[stack.pop()] = nums[idx];
    }

    // Only push on first pass (second pass resolves, doesn't add new waiters)
    if (i < n) stack.push(idx);
  }

  return result;
}

Dry Run: nextGreaterElements([1,2,1])

n=3. result=[-1,-1,-1]. stack=[].

i=0 (idx=0, val=1): stack empty. Push 0. stack=[0].
i=1 (idx=1, val=2): nums[0]=1 < 2. Pop 0. result[0]=2. stack=[]. Push 1. stack=[1].
i=2 (idx=2, val=1): nums[1]=2 > 1. No pop. Push 2. stack=[1,2].

i=3 (idx=0, val=1): i>=n, don't push new entries.
  nums[2]=1 >= 1. No pop (not strictly greater).
  (Actually 1 is not < 1, so no pop.)
i=4 (idx=1, val=2): nums[2]=1 < 2. Pop 2. result[2]=2. ← circular: day 2's next greater is day 1's value ✓
  stack=[1]. nums[1]=2 >= 2. No pop.
i=5 (idx=2, val=1): nums[1]=2 > 1. No pop.

End. stack=[1] → result[1] stays -1. ✓

result=[2,-1,2] ✓

Why process 2n: The second pass gives every element a chance to find its next greater by looking "beyond" the array's end and wrapping around. After 2n passes, if an element still hasn't found its next greater, it genuinely has none (it must be the global maximum, cycling back to itself or something ≤ itself).

Complexity: O(n) time, O(n) space.

Problem 6: Largest Rectangle in Histogram

Problem: Given bar heights, find the largest rectangle you can form.
largestRectangleArea([2,1,5,6,2,3]) → 10
LeetCode 84. Hard. One of the most important stack problems.

Four Questions

Q1: What do I have? An array of non-negative bar heights.
Q2: What do I want? The area of the largest rectangle fitting entirely within the histogram.
Q3: What is the brute force? For each pair (i, j), find the minimum height between them, compute minH * (j-i+1). O(n³) or O(n²) with prefix mins.
Q4: Where is the waste? For each bar as the limiting (shortest) bar: the rectangle extends left until it hits a shorter bar and right until it hits a shorter bar. This is "previous smaller to left" and "next smaller to right" — two monotonic stack passes. Or: one pass with a stack that processes on both ends simultaneously.

The Insight

For bar i to be the shortest bar in a rectangle:

• Rectangle can extend left to index left[i] — the nearest bar shorter than heights[i], exclusive.
• Rectangle can extend right to index right[i] — the nearest bar shorter than heights[i], exclusive.
• Width = right[i] - left[i] - 1.
• Area = heights[i] * width.

function largestRectangleArea(heights) {
  const n = heights.length;
  const stack = [];  // monotonic increasing stack (indices)
  let maxArea = 0;

  for (let i = 0; i <= n; i++) {
    // Sentinel: process remaining stack when i === n (height = 0)
    const currentHeight = i === n ? 0 : heights[i];

    while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
      const height = heights[stack.pop()];
      // Width: from current left boundary to right boundary i
      const width = stack.length === 0
        ? i                          // no left boundary: extends to index 0
        : i - stack[stack.length - 1] - 1;  // left boundary is stack's new top
      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}

Full Dry Run: largestRectangleArea([2,1,5,6,2,3])

heights=[2,1,5,6,2,3]. n=6. stack=[]. maxArea=0.

i=0, h=2: stack empty. Push 0. stack=[0].

i=1, h=1: heights[0]=2 > 1. Pop 0.
  height=2. stack empty → width=1. area=2*1=2. maxArea=2.
  heights for remaining stack: empty. Push 1. stack=[1].

i=2, h=5: heights[1]=1 < 5. Push 2. stack=[1,2].

i=3, h=6: heights[2]=5 < 6. Push 3. stack=[1,2,3].

i=4, h=2:
  heights[3]=6 > 2. Pop 3.
    height=6. stack top=2. width=4-2-1=1. area=6*1=6. maxArea=6.
  heights[2]=5 > 2. Pop 2.
    height=5. stack top=1. width=4-1-1=2. area=5*2=10. maxArea=10.
  heights[1]=1 < 2. Stop.
  Push 4. stack=[1,4].

i=5, h=3: heights[4]=2 < 3. Push 5. stack=[1,4,5].

i=6 (sentinel, h=0):
  heights[5]=3 > 0. Pop 5.
    height=3. stack top=4. width=6-4-1=1. area=3*1=3. maxArea=10.
  heights[4]=2 > 0. Pop 4.
    height=2. stack top=1. width=6-1-1=4. area=2*4=8. maxArea=10.
  heights[1]=1 > 0. Pop 1.
    height=1. stack empty → width=6. area=1*6=6. maxArea=10.
  Push 6. stack=[6]. (sentinel index)

return 10. ✓ (height=5, width=2, covering bars at indices 2 and 3)

The width calculation explained:

When we pop index p at current position i:

• Right boundary: i (current index is the first bar shorter than heights[p] to its right).
• Left boundary: stack.top after pop (the remaining top is the first bar shorter than heights[p] to its left) — or -1 if stack is empty (extends to the left edge).
• Width = right - left - 1 = i - stack.top - 1.

Sentinel: Adding height 0 at position n forces all remaining stack elements to be processed at the end. Without it, bars that never found a shorter right neighbor would stay in the stack unprocessed.

Complexity: O(n) time — each index pushed once and popped at most once. O(n) space.

Problem 7: Decode String

Problem: Given an encoded string, decode it. k[encoded_string] means the encoded_string is repeated k times.
decodeString("3[a2[c]]") → "accaccacc"
LeetCode 394. Nested structure → stack.

Four Questions

Q1: What do I have? A string with k[...] encoding. Brackets can be nested.
Q2: What do I want? The fully decoded string.
Q3: What is the brute force? Repeatedly find innermost brackets and expand. O(n * max_k) per pass, multiple passes.
Q4: Where is the waste? Re-scanning. When we hit [, push current state (current string + current number). When we hit ], pop the state, repeat what's in between, append to the restored string.

function decodeString(s) {
  const countStack = [];   // stack of pending repeat counts
  const stringStack = [];  // stack of pending partial strings
  let currentStr = "";
  let currentNum = 0;

  for (const c of s) {
    if (c >= '0' && c <= '9') {
      currentNum = currentNum * 10 + Number(c);  // handle multi-digit k
    } else if (c === '[') {
      // Save current state, reset for inside-bracket content
      countStack.push(currentNum);
      stringStack.push(currentStr);
      currentNum = 0;
      currentStr = "";
    } else if (c === ']') {
      // Restore: repeat currentStr by the saved count, append to saved string
      const count = countStack.pop();
      const prevStr = stringStack.pop();
      currentStr = prevStr + currentStr.repeat(count);
    } else {
      currentStr += c;
    }
  }

  return currentStr;
}

Full Dry Run: decodeString("3[a2[c]]")

countStack=[], stringStack=[], currentStr="", currentNum=0.

c='3': currentNum=3.
c='[': push countStack=[3], push stringStack=[""]. currentNum=0, currentStr="".
c='a': currentStr="a".
c='2': currentNum=2.
c='[': push countStack=[3,2], push stringStack=["","a"]. currentNum=0, currentStr="".
c='c': currentStr="c".
c=']':
  count=2, prevStr="a".
  currentStr = "a" + "c".repeat(2) = "a" + "cc" = "acc".
  countStack=[3], stringStack=[""].
c=']':
  count=3, prevStr="".
  currentStr = "" + "acc".repeat(3) = "" + "accaccacc" = "accaccacc".
  countStack=[], stringStack=[].

return "accaccacc". ✓

Why currentNum * 10 + digit: The number before [ can be multi-digit (e.g., 100[a]). Reading digits one by one and accumulating gives the full number.

Complexity: O(n * max_k) — each character is output once, but repeat operations can expand the string. Space: O(n) for stacks.

Problem 8: Binary Tree Level Order Traversal (Queue Preview)

Problem: Return a level-by-level array of values in a binary tree.
levelOrder(root) → [[3],[9,20],[15,7]] for the tree with root 3, children 9 and 20, grandchildren 15 and 7.
LeetCode 102.

This previews Chapter 10 (Trees). The queue is the key.

The Insight

Process all nodes at level 0 (root) first. Then all at level 1. Then level 2. FIFO — the queue processes nodes in the order they were discovered.

To separate levels: at the start of each level, note queue.length — that's how many nodes are at this level. Process exactly that many, adding their children to the queue for the next level.

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;  // nodes at current level
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();   // dequeue
      level.push(node.val);
      if (node.left) queue.push(node.left);    // enqueue children
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

Why queue (not stack): Stack would give depth-first traversal — we'd go all the way down one branch before processing the sibling. Queue gives breadth-first — we stay at one level until it's fully processed.

Complexity: O(n) time (each node visited once), O(w) space where w is the maximum width of the tree (maximum nodes at any level — worst case n/2 for a perfect binary tree).

Pattern Recognition Decision Tree

New stack/queue problem:

1. Does the problem involve NESTING or MATCHING?
   → Stack. Push on open, pop on close. Check match on pop.

2. "For each element, find nearest greater/smaller left or right"?
   → Monotonic stack. Decide direction (L→R or R→L) and invariant (increasing or decreasing).

3. "Process elements and some of them will be resolved by future elements"?
   → Monotonic stack. Push "waiting" elements; resolve on trigger.

4. Do you need min/max of the current stack contents in O(1)?
   → Augment with parallel min/max stack.

5. Does the problem have nested structure (like brackets or k[...] encoding)?
   → Two stacks or push current state on open, restore on close.

6. Process in arrival order? Shortest path? Level-by-level?
   → Queue.

7. Told to "implement queue using stacks" or "implement stack using queues"?
   → Two-structure pattern. Know the amortized analysis.

5 Practice Problems

1. Trace and Predict

function f(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = [];
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && temperatures[stack[stack.length-1]] <= temperatures[i]) {
      stack.pop();
    }
    result[i] = stack.length === 0 ? -1 : stack[stack.length-1];
    stack.push(i);
  }
  return result;
}

Trace f([73,74,75,71,69,72,76,73]). What does this function compute? How does it differ from Daily Temperatures? What is the monotonic invariant of the stack? What is returned for the element with no valid answer?

2. Find the Waste

Brute force for "next greater element": O(n²). After seeing the monotonic stack solution (O(n)), trace where each "wasted" comparison in the brute force is saved. Specifically, for [2,1,2,4,3], list every (i,j) comparison the brute force makes, then mark which ones the monotonic stack avoids and why it's safe to skip them.

3. Failure Analysis

function isValid(s) {
  const stack = [];
  for (const c of s) {
    if ('([{'.includes(c)) stack.push(c);
    else {
      const top = stack.pop();
      if (c === ')' && top !== '(') return false;
      if (c === ']' && top !== '[') return false;
      if (c === '}' && top !== '{') return false;
    }
  }
  return stack.length === 0;
}

This has a bug. Find the input that breaks it. Fix it. (Hint: what happens when you call stack.pop() on an empty stack in JavaScript? What does it return?)

4. Design Under Constraints

Design asteroidCollision(asteroids) (LeetCode 735): given an array of integers representing asteroids (positive = moving right, negative = moving left, absolute value = size), simulate collisions. When two asteroids meet (positive then negative), the smaller explodes. If equal, both explode.

asteroidCollision([5,10,-5]) → [5,10] (10 survives, -5 explodes).
asteroidCollision([8,-8]) → [] (both explode).
asteroidCollision([10,2,-5]) → [10] (2 explodes, then 5 explodes against 10).

Write the solution using a stack. When is a collision possible? When does it not happen? Walk through each case.

5. Reach Beyond

trappingRainWater (LeetCode 42) can be solved in O(n) time O(1) space with two pointers (Chapter 5a practice). It can also be solved with a monotonic stack. Design the stack solution:

For each bar, the water above it is bounded by the shorter of the tallest bar to its left and to its right. When can the stack "settle" a computation? (Hint: when a taller bar arrives, the bar in the valley between the current bar and the stack top can be computed.) Work through [0,1,0,2,1,0,1,3,2,1,2,1] → 6.

Compare the three approaches to trapping rain water: prefix/suffix max arrays (O(n) space from Ch 2a), two pointers (O(1) space from Ch 5a practice), and monotonic stack. Which would you use in an interview and why?