Stack — The Complete Guide

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

  for (const ch of s) {
    if (ch in pairs) {
      // Closing bracket — pop and check match
      if (stack.length === 0 || stack.pop() !== pairs[ch]) {
        return false;
      }
    } else {
      // Opening bracket — push
      stack.push(ch);
    }
  }

  return stack.length === 0; // no unmatched openers
}
// When to use: valid parentheses, valid tag nesting,
// balanced brackets, matching delimiters

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

  for (let i = 0; i < n; i++) {
    // Pop elements smaller than current — current is their "next greater"
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop()!;
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  return result;
}
// Variation: for "next smaller", flip the comparison to <
// Variation: for "previous greater", iterate right-to-left
// When to use: daily temperatures, next greater element,
// stock span, largest rectangle in histogram

function calculate(s: string): number {
  const stack: number[] = [];
  let num = 0;
  let sign = 1;
  let result = 0;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + Number(ch);
    } else if (ch === '+' || ch === '-') {
      result += sign * num;
      num = 0;
      sign = ch === '+' ? 1 : -1;
    } else if (ch === '(') {
      // Save current state and start fresh
      stack.push(result);
      stack.push(sign);
      result = 0;
      sign = 1;
    } else if (ch === ')') {
      result += sign * num;
      num = 0;
      // Restore previous state
      result *= stack.pop()!; // sign before '('
      result += stack.pop()!; // result before '('
    }
  }

  return result + sign * num;
}
// When to use: basic calculator I/II/III,
// evaluate reverse polish notation, decode string

function simplifyPath(path: string): string {
  const stack: string[] = [];
  const parts = path.split("/");

  for (const part of parts) {
    if (part === "..") {
      stack.pop(); // go up one directory
    } else if (part !== "" && part !== ".") {
      stack.push(part); // enter directory
    }
    // skip empty strings and "." (current directory)
  }

  return "/" + stack.join("/");
}
// When to use: simplify path, backspace string compare,
// remove all adjacent duplicates, asteroid collision

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

  for (let i = 0; i <= n; i++) {
    // Use 0 as sentinel for the final cleanup pass
    const currHeight = i === n ? 0 : heights[i];

    while (stack.length > 0 && currHeight < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()!];
      // Width: from the element below in stack to current index
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}
// Time: O(n) — each bar is pushed and popped at most once
// Space: O(n) — stack holds at most n indices
// Key: when a bar is popped, the current index is its "next smaller on right"
// and the new stack top is its "next smaller on left".

function decodeString(s: string): string {
  const countStack: number[] = [];
  const stringStack: string[] = [];
  let currentStr = "";
  let k = 0;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      k = k * 10 + Number(ch);
    } else if (ch === '[') {
      // Save current state and start fresh
      countStack.push(k);
      stringStack.push(currentStr);
      currentStr = "";
      k = 0;
    } else if (ch === ']') {
      // Pop and repeat
      const repeatCount = countStack.pop()!;
      const prevStr = stringStack.pop()!;
      currentStr = prevStr + currentStr.repeat(repeatCount);
    } else {
      currentStr += ch;
    }
  }

  return currentStr;
}
// Time: O(n × maxRepeat) — building the decoded string
// Space: O(n) — stack depth equals nesting depth
// Key: '[' saves state (push), ']' restores and combines (pop).

function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];

  for (const ast of asteroids) {
    let alive = true;

    while (alive && ast < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];
      if (top < Math.abs(ast)) {
        stack.pop(); // top asteroid explodes, keep checking
      } else if (top === Math.abs(ast)) {
        stack.pop(); // both explode
        alive = false;
      } else {
        alive = false; // incoming asteroid explodes
      }
    }

    if (alive) stack.push(ast);
  }

  return stack;
}
// Time: O(n) — each asteroid is pushed/popped at most once
// Space: O(n) — stack holds surviving asteroids
// Key: only right-moving (positive) vs left-moving (negative) collide.
// Same direction or left-then-right never collide.

Input: "({[]})"

Step 1: ch = '(' → opening bracket → push
  stack = ['(']

Step 2: ch = '{' → opening bracket → push
  stack = ['(', '{']

Step 3: ch = '[' → opening bracket → push
  stack = ['(', '{', '[']

Step 4: ch = ']' → closing bracket → pop '[', check: pairs[']'] = '[' ✓
  stack = ['(', '{']

Step 5: ch = '}' → closing bracket → pop '{', check: pairs['}'] = '{' ✓
  stack = ['(']

Step 6: ch = ')' → closing bracket → pop '(', check: pairs[')'] = '(' ✓
  stack = []

Stack is empty → VALID ✓

Key: Each closer matches the MOST RECENT opener — that's LIFO.
The stack naturally handles arbitrary nesting depth.

Input: temps = [73, 74, 75, 71, 69, 72, 76, 73]
result = [0, 0, 0, 0, 0, 0, 0, 0]
stack = [] (stores indices)

i=0: temp=73, stack empty → push 0
  stack = [0]

i=1: temp=74 > temps[0]=73 → pop 0, result[0] = 1-0 = 1
  stack empty, push 1
  stack = [1]    result = [1,0,0,0,0,0,0,0]

i=2: temp=75 > temps[1]=74 → pop 1, result[1] = 2-1 = 1
  stack empty, push 2
  stack = [2]    result = [1,1,0,0,0,0,0,0]

i=3: temp=71 < temps[2]=75 → no pop, push 3
  stack = [2,3]

i=4: temp=69 < temps[3]=71 → no pop, push 4
  stack = [2,3,4]

i=5: temp=72 > temps[4]=69 → pop 4, result[4] = 5-4 = 1
  temp=72 > temps[3]=71 → pop 3, result[3] = 5-3 = 2
  temp=72 < temps[2]=75 → stop, push 5
  stack = [2,5]  result = [1,1,0,2,1,0,0,0]

i=6: temp=76 > temps[5]=72 → pop 5, result[5] = 6-5 = 1
  temp=76 > temps[2]=75 → pop 2, result[2] = 6-2 = 4
  stack empty, push 6
  stack = [6]    result = [1,1,4,2,1,1,0,0]

i=7: temp=73 < temps[6]=76 → no pop, push 7
  stack = [6,7]  result = [1,1,4,2,1,1,0,0]

Done. Indices 6,7 remain on stack → no warmer day → result stays 0.

Answer: [1, 1, 4, 2, 1, 1, 0, 0]

Key: The stack always holds indices in DECREASING temperature order.
When a warmer day arrives, it resolves all cooler days waiting on the stack.

Input: heights = [2, 1, 5, 6, 2, 3]
stack = [], maxArea = 0

i=0: h=2, stack empty → push 0
  stack = [0]

i=1: h=1 < heights[0]=2 → pop 0
  height=2, width=1 (stack empty, so width=i=1)
  area = 2×1 = 2, maxArea = 2
  push 1
  stack = [1]

i=2: h=5 > heights[1]=1 → push 2
  stack = [1,2]

i=3: h=6 > heights[2]=5 → push 3
  stack = [1,2,3]

i=4: h=2 < heights[3]=6 → pop 3
  height=6, width = 4-2-1 = 1, area = 6, maxArea = 6
  h=2 < heights[2]=5 → pop 2
  height=5, width = 4-1-1 = 2, area = 10, maxArea = 10
  h=2 ≥ heights[1]=1 → stop, push 4
  stack = [1,4]

i=5: h=3 > heights[4]=2 → push 5
  stack = [1,4,5]

i=6 (sentinel h=0): pop 5
  height=3, width = 6-4-1 = 1, area = 3
  pop 4: height=2, width = 6-1-1 = 4, area = 8
  pop 1: height=1, width = 6 (stack empty), area = 6

maxArea = 10

Answer: 10 (the 5×2 rectangle spanning bars at index 2 and 3)

Key: When a bar is popped, its left boundary is the new stack top
and its right boundary is the current index.

Does the problem involve matching or validating nested tokens?
├── YES → Bracket Matching template (push openers, pop on closers)
└── NO  → Does the problem ask for "next greater" or "next smaller" element?
          ├── YES → Monotonic Stack (decreasing for next greater, increasing for next smaller)
          └── NO  → Does the problem involve evaluating an expression or calculator?
                    ├── YES → Expression Evaluation template (number stack + operator handling)
                    └── NO  → Does the problem involve undoing, backtracking, or simplifying?
                              ├── YES → Undo/State template (push valid items, pop to undo)
                              └── NO  → Does the problem involve computing areas or spans based on boundaries?
                                        ├── YES → Monotonic Stack (histogram pattern)
                                        └── NO  → Does the problem have nested/recursive structure?
                                                  ├── YES → State-saving stack (push on open, pop on close)
                                                  └── NO  → Stack probably isn't the right pattern
                                                            → Consider Queue, Heap, or Two Pointers