Stacks: Matching Pairs and the Next Greater Element

The problem

Valid Parentheses: is "{[()]}" balanced? What about "([)]"? Every closing bracket must match the most recent opening bracket that is still open. "Most recent first" is exactly what a stack does.

How to spot it

• Matching pairs: brackets, HTML tags, "remove adjacent duplicates"
• Something must be undone or resolved in reverse order (undo history, backspace strings)
• "Next greater / next smaller element", "how many days until a warmer temperature", stock span
• Evaluating expressions, decoding nested strings like 3[a2[c]]

The idea

A stack is a pile of plates: you add to the top and take from the top. Push things that are still "waiting"; pop them when the thing that resolves them arrives.

Monotonic stack: to find, for each element, the next element that is bigger, keep a stack of indexes still waiting for their answer. Their values are in decreasing order. When a bigger value arrives, it is the answer for everything smaller on top of the stack, so pop them and record it. Each index is pushed and popped once: O(n).

The template

# matching
stack = []
for ch in s:
    if opens(ch):
        stack.append(ch)
    elif not stack or stack.pop() != partner(ch):
        return False
return not stack                 # nothing left open

# next greater element (monotonic stack of indexes)
answer = [-1] * len(nums)
waiting = []
for i, x in enumerate(nums):
    while waiting and nums[waiting[-1]] < x:
        answer[waiting.pop()] = x
    waiting.append(i)

// matching
const stack = [];
for (const ch of s) {
  if (opens(ch)) stack.push(ch);
  else if (!stack.length || stack.pop() !== partner(ch)) return false;
}
return stack.length === 0;       // nothing left open

// next greater element (monotonic stack of indexes)
const answer = new Array(nums.length).fill(-1);
const waiting = [];
nums.forEach((x, i) => {
  while (waiting.length && nums[waiting.at(-1)] < x) answer[waiting.pop()] = x;
  waiting.push(i);
});

Worked example

Bracket matching, and "daily temperatures": for each day, how many days until a warmer one?

PAIRS = {")": "(", "]": "[", "}": "{"}


def is_valid(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != PAIRS[ch]:
            return False
    return not stack


def daily_temperatures(temps):
    wait = [0] * len(temps)
    waiting = []                          # indexes of colder days still waiting
    for day, t in enumerate(temps):
        while waiting and temps[waiting[-1]] < t:
            colder = waiting.pop()
            wait[colder] = day - colder   # today is the warmer day they waited for
        waiting.append(day)
    return wait


for s in ["{[()]}", "([)]", "((", "()[]{}"]:
    print(s, "valid" if is_valid(s) else "invalid")
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))

{[()]} valid
([)] invalid
(( invalid
()[]{} valid
[1, 1, 4, 2, 1, 1, 0, 0]

const PAIRS = { ")": "(", "]": "[", "}": "{" };

function isValid(s) {
  const stack = [];
  for (const ch of s) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (!stack.length || stack.pop() !== PAIRS[ch]) return false;
  }
  return stack.length === 0;
}

function dailyTemperatures(temps) {
  const wait = new Array(temps.length).fill(0);
  const waiting = [];                       // indexes of colder days still waiting
  temps.forEach((t, day) => {
    while (waiting.length && temps[waiting.at(-1)] < t) {
      const colder = waiting.pop();
      wait[colder] = day - colder;          // today is the warmer day they waited for
    }
    waiting.push(day);
  });
  return wait;
}

for (const s of ["{[()]}", "([)]", "((", "()[]{}"]) console.log(s, isValid(s) ? "valid" : "invalid");
console.log(JSON.stringify(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])).replaceAll(",", ", "));

{[()]} valid
([)] invalid
(( invalid
()[]{} valid
[1, 1, 4, 2, 1, 1, 0, 0]

Common mistakes

• Popping an empty stack. A closing bracket with nothing open is invalid; check before popping.
• Forgetting leftovers. "((" never fails during the loop; it fails because the stack isn't empty at the end.
• Storing values instead of indexes in a monotonic stack when you need distances or positions.
• Using a queue by mistake. Matching needs the most recent item (stack), not the oldest (queue).

Practice

• Valid Parentheses (easy)
• Daily Temperatures (medium)
• Min Stack (medium): keep a second stack of "minimum so far".

Key points

• Stack = most recent unfinished thing; push when opened, pop when resolved.
• Valid only if every pop matches and the stack ends empty.
• Monotonic stack: pop everything the new element "answers"; each index moves once, so O(n).
• Store indexes when you need distances.