The Stack That Remembers

When a question says "in one pass" or "without nested loops", two structures are usually doing the work: a stack for decisions you must postpone, and a hash map for facts you must remember. They look like data structures; behave like them as a sentence each — what is waiting, and where have I been.

A stack is unfinished business

Balanced delimiters are the canonical case. An opener is a promise: some closer will settle me later. Promises settle in reverse order — the most recent opener is the one a closer must match — and last-in-first-out is exactly reverse-settlement.

export function isBalanced(input: string): boolean {
  const open: string[] = []
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }

  for (const ch of input) {
    if (ch === '(' || ch === '[' || ch === '{') {
      open.push(ch)
    } else if (pairs[ch] !== undefined) {
      if (open.pop() !== pairs[ch]) return false
    }
  }
  return open.length === 0
}

Three endings, three diagnoses: a closer that mismatches (the pop returns the wrong opener), a closer with nothing open (the pop returns undefined), and an opener that never settled (open.length !== 0 at the end — the forgotten check). Each ending is a different bug in the input, and the structure distinguishes them for free.

} else if (pairs[ch] !== undefined) {
  if (open.() !== pairs[ch]) return false
}

The monotonic stack: everyone is waiting for something bigger

The trick with a name: "for each element, how far until something bigger?" Keep a stack of elements still waiting. When a bigger one arrives, it is the answer for every waiting element it dominates — pop them, answer them, then join the stack yourself.

export function warmerIn(temperatures: number[]): number[] {
  const answer = Array.from<number>({ length: temperatures.length }).fill(0)
  const pending: number[] = []

  for (let i = 0; i < temperatures.length; i++) {
    const temp = temperatures[i] as number
    while (
      pending.length > 0 &&
      (temperatures[pending[pending.length - 1] as number] as number) < temp
    ) {
      const waiting = pending.pop() as number
      answer[waiting] = i - waiting
    }
    pending.push(i)
  }
  return answer
}

The non-obvious part is what the stack is while it waits: strictly decreasing temperatures from bottom to top. Nothing enforces that — it falls out of the pops. A new arrival pops everything it beats, so anything left unbeaten is bigger. That emergent order is why the structure is called monotonic, and it is also your debug instrument: a waiting stack that is not decreasing is a popped-too-little bug. Note the strict <: an equal day is not warmer, so it waits — with <= a plateau releases its members one day early.

A hash map is where you have been

The two-sum question in its honest form: for each number, the question is not "does a partner exist?" but "have I already seen the partner?" — and seen is a lookup.

export function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>()

  for (let i = 0; i < nums.length; i++) {
    const need = target - (nums[i] as number)
    if (seen.has(need)) return [seen.get(need) as number, i]
    seen.set(nums[i] as number, i)
  }
  return null
}

The order inside the loop is the whole correctness: look before you write. Write first, and a number that is exactly half the target finds the entry you just made — the element paired with itself. This one-line reorder is the most common review finding in hash-map code, and it is worth internalizing as a rule: the map holds the past, and this iteration is not the past until it ends.

const need = target - (nums[i] as number)
if (seen.has(need)) return [seen.get(need) as number, i]
seen.(nums[i] as number, i)

How to debug both

Print the stack on every push and pop, annotated with why. For the monotonic stack, print it as the values it holds — "waiting: 73, 74" — and check the ordering invariant out loud; the iteration where order breaks is the iteration where your comparison is backwards. For a hash map, print the lookup key and the map's size: a map that grows to the input size before any hit means the lookup key never matches what you stored — usually the key computed from the wrong side of the relation. In the exercises for this concept, the discriminating tests are named: pairs an element with itself, does not count an equal day as warmer. Read them after your first failure; they are the pattern's edges stated as code.

Where this bites

• Reading the map before writing it. The self-pairing bug: a value that is half the target matches the entry this same iteration just inserted. Counter: the lookup and the insert are one ordered unit — lookup, return, insert, in that order, adjacent lines.
• Popping on equality. In a monotonic stack, equal values do not resolve each other; releasing them early answers "one day early" for the plateau. Counter: decide strictly-what-counts-as-resolution before writing the loop, and use the strict comparison when "strictly bigger" is the question.
• Forgetting the leftovers. A stack that ends non-empty is an answer too — those elements never found their resolution, and for "how far until warmer" the answer is zero. Counter: initialize the result array with the never-resolved value, so the leftover case needs no code at all.
• Balanced-input checks that stop early. Returning true the moment the input ends ignores openers that never closed. Counter: the structure's final state is part of the contract — check emptiness after the loop, not just mismatches inside it.