Stacks: the most recent unfinished thing

A stack is a list where you only add and remove at one end, called the top. The last item you put in is the first one you take out. This is called “last in, first out”. So a stack always hands you the most recent thing that is still unfinished.

Think of it like this: a pile of plates in a canteen. Clean plates go on top, and the next person takes the top plate. Nobody pulls a plate out of the middle.

How to spot it

Words and constraints in a problem that point to this pattern:

• Brackets or tags that must be “balanced”, “valid” or “properly nested”
• “Undo”, “backspace” or “go back”: the newest thing is the one you need next
• “Next greater element”, “next warmer day”, “how many days until…”: for each item, the first later item that beats it
• Evaluating an expression where an operator works on the two most recent numbers
• Neighbours that cancel or combine, like “remove adjacent duplicates”

Watch it work

The template

// The basic operations on a JavaScript array used as a stack
const demo: string[] = [];
demo.push("a");                      // stack: [a]
demo.push("b");                      // stack: [a, b]   (b is on top)
const top = demo[demo.length - 1];   // peek: "b", the stack is unchanged
const removed = demo.pop();          // "b" comes off; stack: [a]

// Monotonic stack: for each item, the first later item that is bigger
function nextGreater(nums: number[]): number[] {
  const answer: number[] = new Array(nums.length).fill(-1); // -1 means "nothing bigger to the right"
  const stack: number[] = [];        // indexes still waiting for their answer
  for (let i = 0; i < nums.length; i++) {
    // While the current number beats the number on top, the top has found its answer
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const waiting = stack.pop()!;  // the index that was waiting
      answer[waiting] = nums[i];     // record what this problem asks for
    }
    stack.push(i);                   // now the current index waits for its own answer
  }
  return answer;                     // anything left on the stack keeps -1
}

Worked example

1. The natural first try: find a pair, cut it out, and start scanning again from the beginning. "abbaca" becomes "aaca", then "ca". Each cut builds a new string, which takes up to n steps. You may need n / 2 cuts, so this is O(n²).

   function removePairsSlow(s: string): string {
     let changed = true;
     while (changed) {
       changed = false;
       for (let i = 0; i + 1 < s.length; i++) {
         if (s[i] === s[i + 1]) {
           s = s.slice(0, i) + s.slice(i + 2); // cut the pair out
           changed = true;
           break; // and scan again from the start
         }
       }
     }
     return s;
   }
   

2. Notice the waste. After "bb" disappears, the only new pair that can form is between the letter before the pair and the letter after it. So each new letter only needs comparing with the most recent letter you kept. “Most recent kept” is the top of a stack.

3. Walk the string once. If the letter equals the top of the stack, the two cancel: pop. Otherwise push it. At the end, the stack holds the answer in order.

   function removePairs(s: string): string {
     const stack: string[] = [];
     for (const ch of s) {
       if (stack.length > 0 && stack[stack.length - 1] === ch) {
         stack.pop();    // ch cancels with the letter before it
       } else {
         stack.push(ch); // keep ch; it may cancel with a later letter
       }
     }
     return stack.join("");
   }
   

4. Check it on "abbaca": a → [a], b → [a, b], b matches the top → [a], a matches the top → [], c → [c], a → [c, a]. Joined: "ca". Correct, in one pass.

5. Edge cases: "aaaa" cancels down to an empty stack and returns "". An empty input never enters the loop and also returns "". The stack.length > 0 check stops you comparing against an empty stack.

Common mistakes

• Reading the top of an empty stack: stack[stack.length - 1] is undefined, and a comparison with it quietly gives a wrong answer. Check stack.length > 0 first.
• Pushing values when the problem needs distances: for “how many days until warmer” you need i - waiting, so push indexes and read values with nums[index].
• Using if instead of while in a monotonic stack: one big number can answer several waiting items, so if answers only one and leaves the rest wrong.
• Forgetting the items still on the stack at the end. They never found an answer, so they need the default, such as -1 or 0. It's easiest to set that default when you create the answer array.
• Using unshift() and shift() to work at the front of the array: it still behaves like a stack. But each call moves every element, so a 100,000-item input becomes slow.

Cost

In interviews