DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 5 of 16 · ~3 min

Stacks & Monotonic Stack

Last-in-first-out ordering earns its keep the moment the prerequisite system grows past simple pairs into full boolean expressions typed by advisors: (CS101 AND (CS201 OR MATH201)).

Where a stack does a recursive parser's job, more safely

Before the planner can interpret that expression, it needs to confirm the parentheses actually nest correctly:

function isValidPrereqExpression(expr) {
  const stack = [];
  for (const ch of expr) {
    if (ch === '(') {
      stack.push(ch);
    } else if (ch === ')') {
      if (stack.length === 0) return false;   // a close with nothing left open to match it
      stack.pop();
    }
  }
  return stack.length === 0;    // every opener needs to have found its closer
}

isValidPrereqExpression('(CS101 AND (CS201 OR MATH201))');  // true
isValidPrereqExpression('(CS101 AND MATH201))');             // false — a stray close

Functionally this is a recursive parser, just with the call stack swapped for an array you manage yourself — and that swap buys something real. A recursive version leans on the language runtime's own call stack, and every runtime caps how deep that stack can go before it gives up — the exact ceiling varies by engine, but it's a real number, not an infinite resource. An advisor pasting in a deeply nested rule, or one a script generated automatically, can walk straight into that ceiling. The array-based version above answers to no such limit; it keeps going until ordinary memory runs out, which in practice never happens for a prerequisite string.

Monotonic stack — finding the next heavier day

A monotonic stack keeps one invariant alive — always increasing, or always decreasing, bottom to top — and evicts whatever breaks that invariant the instant a new element arrives. Eviction is the moment that element's answer becomes known.

The workload warning feature wants, for every day of term, how many days until a heavier one shows up — the number that tells a student whether today's light load is a good day to get ahead, or whether tomorrow is worse anyway:

function daysUntilHeavierLoad(dailyCreditLoads) {
  const result = new Array(dailyCreditLoads.length).fill(-1);
  const stack = [];   // holds INDICES; the loads they point to stay decreasing, bottom to top

  for (let i = 0; i < dailyCreditLoads.length; i++) {
    while (stack.length && dailyCreditLoads[stack[stack.length - 1]] < dailyCreditLoads[i]) {
      const idx = stack.pop();
      result[idx] = i - idx;      // day i is idx's answer
    }
    stack.push(i);
  }
  return result;
}

On the page, a while loop living inside a for loop reads as O(n²) by reflex. Resist that reflex here: over the life of the whole function, each index gets pushed exactly once and can only ever be popped once, so no matter how the pops distribute themselves across different iterations of the outer loop, they can't add up to more than n total. That caps the entire function at O(n) — the same trick the variable-size window used earlier, tallying every push and pop across the full run instead of pricing one iteration in isolation.

Recognize this shape by: "next greater/smaller," "how many steps until things improve," "nearest larger value in this direction" — any question asking, for every element, where the nearest qualifying neighbor sits. A plain double loop answers it in O(n²); the monotonic stack gets there in O(n) by never looking at an element twice once its fate is settled.

Stacks on Code Lab has the drill set.