🥞 Stack & Monotonic Stack

A learning sheet — a stack remembers what's unresolved and settles it in reverse. The monotonic variant turns O(n²) "nearest larger/smaller" scans into one pass.

🧠 1 · How to think (and invent it)

The plain idea: a stack is "things I've seen but can't finish yet," resolved last-in-first-out. Openers wait for closers; a sub-expression waits until its ]; the call stack waits for each return.

The powerful idea — the monotonic stack: keep the stack sorted (always increasing, or always decreasing). When a newcomer would break that order, pop the elements it dominates and resolve each one against the newcomer. Because every element is pushed once and popped once, an apparently nested loop is actually O(n).

Watch it get invented — Daily Temperatures

For each day, how many days until a warmer one? temps = [73,74,75,71,69,72,76,73].

1. Start brute. For each i, scan right for the first warmer day → O(n²), re-scanning the same cold stretch over and over.
2. Spot the waste. Keep a stack of days still waiting for a warmer one — naturally in decreasing temperature. A warm newcomer resolves all the colder days on top at once, and a day is resolved exactly once.
3. The leap. Decreasing stack of indices. While temps[top] < temps[i]: pop, set ans[top] = i − top. Then push i.
4. Payoff. Each index pushed once, popped once ⇒ O(n).

Answer: [1,1,4,2,1,1,0,0]. Days never resolved (no warmer ahead) keep their default 0.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

§4.3–4.5 are the monotonic family — same engine (push-once/pop-once), different "what you compute on pop." Each pattern: a one-liner, a 🔑 invariant, a template, and a 🎤 interview lens.

4.1 · Matching & nesting

“Push what's open; a closer must match the most recent opener.”

Setup: the only thing that can close an opener is the nearest unclosed one — pure LIFO.

function isValid(s: string): boolean {
  const stack: string[] = [];
  const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  for (const c of s) {
    if (c in match) { if (stack.pop() !== match[c]) return false; }  // closer: must match top
    else stack.push(c);                                             // opener: wait
  }
  return stack.length === 0;   // nothing left unclosed
}

4.2 · Parse / evaluate — a stack of context

“Hit a sub-part — stash what you were doing; finish it; pop and resume.”

Setup: when you descend into a bracketed/nested piece, push the surrounding state; when it ends, pop and splice the result back.

// Decode String:  "3[a2[c]]" -> "accaccacc"
function decodeString(s: string): string {
  const numStack: number[] = [], strStack: string[] = [];
  let cur = '', num = 0;
  for (const c of s) {
    if (c >= '0' && c <= '9') num = num * 10 + (+c);           // multi-digit
    else if (c === '[') { numStack.push(num); strStack.push(cur); num = 0; cur = ''; } // descend
    else if (c === ']') { const k = numStack.pop()!; cur = strStack.pop()! + cur.repeat(k); } // resume
    else cur += c;
  }
  return cur;
}

4.3 · Monotonic stack — nearest greater / smaller

“A newcomer resolves everyone it dominates, all at once.”

Setup: maintain a stack of indices whose answers aren't known yet, kept monotonic. The newcomer pops (and answers) every waiting element it beats.

// Next Greater Element — res[i] = next value to the right greater than a[i], else -1
function nextGreater(a: number[]): number[] {
  const res = new Array(a.length).fill(-1);
  const stack: number[] = [];                 // indices; a[stack] strictly decreasing
  for (let i = 0; i < a.length; i++) {
    while (stack.length && a[stack[stack.length - 1]] < a[i]) {
      res[stack.pop()!] = a[i];                // a[i] is the answer for the popped index
    }
    stack.push(i);
  }
  return res;                                   // anything left has no greater → stays -1
}

4.4 · Monotonic stack — spans & areas

“When a bar pops, that's the instant its full width is known.”

Setup: an increasing stack of indices. When a shorter bar arrives, each taller bar it pops can't extend further right — so compute its rectangle at the pop: width = (current index) − (index below it on the stack) − 1.

// Largest Rectangle in Histogram
function largestRectangle(h: number[]): number {
  const stack: number[] = [];          // indices; heights increasing
  let best = 0;
  for (let i = 0; i <= h.length; i++) {
    const cur = i === h.length ? 0 : h[i];          // sentinel 0 flushes the stack
    while (stack.length && h[stack[stack.length - 1]] >= cur) {
      const height = h[stack.pop()!];
      const left = stack.length ? stack[stack.length - 1] : -1;  // nearest shorter on left
      best = Math.max(best, height * (i - left - 1));            // width spans (left, i)
    }
    stack.push(i);
  }
  return best;
}

4.5 · Monotonic stack — greedy lexicographic build

“Build the result greedily; pop a worse predecessor while you still can.”

Setup: construct an output by pushing characters; before pushing, pop earlier characters that are "worse" than the newcomer if your removal budget allows. The stack is the answer-in-progress.

// Remove K Digits — smallest number after deleting k digits
function removeKdigits(num: string, k: number): string {
  const stack: string[] = [];
  for (const d of num) {
    while (k > 0 && stack.length && stack[stack.length - 1] > d) { stack.pop(); k--; } // drop bigger predecessors
    stack.push(d);
  }
  while (k-- > 0) stack.pop();                       // leftover budget → trim the tail (digits ascending)
  return stack.join('').replace(/^0+/, '') || '0';  // strip leading zeros
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 1944 Number of Visible People in a Queue — scan RIGHT→LEFT, decreasing stack
function canSeePersonsCount(h: number[]): number[] {
  const res: number[] = new Array(h.length).fill(0), st: number[] = [];
  for (let i = h.length - 1; i >= 0; i--) {
    while (st.length && h[st[st.length - 1]] < h[i]) { st.pop(); res[i]++; }   // every shorter person is visible
    if (st.length) res[i]++;                                                    // plus the first person >= me
    st.push(i);
  }
  return res;
}

// 636 Exclusive Time of Functions — simulate the call stack
function exclusiveTime(n: number, logs: string[]): number[] {
  const res: number[] = new Array(n).fill(0), st: number[] = [];
  let prev = 0;
  for (const log of logs) {
    const [id, type, t] = log.split(':'); const ts = +t;
    if (type === 'start') {
      if (st.length) res[st[st.length - 1]] += ts - prev;   // caller runs until the callee starts
      st.push(+id); prev = ts;
    } else {
      res[st.pop()!] += ts - prev + 1;                       // end timestamp is INCLUSIVE
      prev = ts + 1;
    }
  }
  return res;
}

// 768 Max Chunks To Make Sorted II — each stack element = the MAX of one chunk
function maxChunksToSorted(arr: number[]): number {
  const st: number[] = [];
  for (const x of arr) {
    if (!st.length || x >= st[st.length - 1]) { st.push(x); continue; }   // >= keeps duplicates in separate chunks
    const cur = st[st.length - 1];                                         // the merged chunk's max
    while (st.length && st[st.length - 1] > x) st.pop();                   // absorb every chunk whose max exceeds x
    st.push(cur);
  }
  return st.length;
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• matching isValid (brackets)
• parse decodeString
• monotonic nextGreater + Daily Temperatures
• area largestRectangle (with the sentinel)
• greedy removeKdigits

For each monotonic one: write "increasing/decreasing, pop on < or ≤, what I compute on pop" as a comment first.