Stacks

Keep unfinished items in last-in, first-out order, so the most recent one is always the next to resolve.

Start with the first problem

Draft. This pattern and its problems have not been reviewed by a second person yet.

A stack fits whenever the thing that most recently opened is the first thing that must close: a bracket, a function call, a transaction inside another transaction. Push when something opens; when something closes, it must match the item on top.

In JavaScript an array is a stack: push adds to the top, pop removes from it, and stack[stack.length - 1] looks without removing. Both ends of the work are one step each.

A second use is the monotonic stack: items still waiting for an answer, kept in order. When a new item arrives, pop every waiting item it answers, then push it to wait in turn. Each item is pushed once and popped at most once, so a question like "how long until something larger" takes one pass instead of a scan per item.

Check what is left at the end. A stack that is not empty means something opened and never closed, or some items never got an answer.

Recognise it

  • Things open and close, and must close in the reverse order they opened.
  • For each item you need the next or previous item that is larger or smaller.
  • A direct solution scans forward from every item.

The shape of the code

const stack = [];
for (let i = 0; i < items.length; i++) {
  while (stack.length && resolves(items[i], items[stack[stack.length - 1]])) {
    const waiting = stack.pop();
    // record the answer for waiting
  }
  stack.push(i);
}
// whatever is left in stack has no answer

Problems

In order of difficulty
  1. Not started
  2. Not started
Esc
↑ ↓ to move↵ to open