Stacks and monotonic stacks

Nesting, and 'the next larger element' in linear amortised time.

Trigger in the prompt: 'Balanced brackets', 'next greater', 'largest rectangle'.

easyValid Parentheses

Decide whether a string of brackets is correctly balanced and nested.

Trigger

'Balanced', 'matching brackets', 'valid nesting'.

Approach
  1. Push opening brackets; on a closing bracket, pop and check the pair matches.
  2. Two failure cases: popping an empty stack, and a non-empty stack at the end.
  3. A dict from closing to opening keeps it short.
Target complexity

O(n) time, O(n) space.

Pitfall

Only counting brackets. '([)]' has equal counts and is invalid — nesting is the point.

Say it out loud

“Counting isn't enough, because nesting matters — bracket-paren-bracket-paren has balanced counts and is invalid. A stack captures the nesting directly, and the two failure modes are popping empty and finishing non-empty.”

Solve on LeetCode
mediumDaily Temperatures

For each day, find how many days until a warmer temperature.

Trigger

'Next greater element', 'how long until something larger'.

Approach
  1. Brute force is O(n²). Say it first.
  2. Monotonic decreasing stack of indices. On a warmer day, pop everything colder and record the gap.
  3. Justify the linear bound with amortised analysis: each index is pushed once and popped once.
Target complexity

O(n) time, O(n) space.

Pitfall

Claiming O(n²) because of the inner `while`. The amortised argument is exactly what is being tested here.

Say it out loud

“This is the next-greater-element pattern with a monotonic stack. The bound is worth defending: there's a nested while loop, but each index is pushed once and popped once, so the total work across the whole loop is linear.”

Solve on LeetCode
hardLargest Rectangle in Histogram

Find the largest rectangle that fits inside a histogram.

Trigger

'Largest area', bars of varying height.

Approach
  1. For each bar, the rectangle using it as the height extends until a shorter bar on each side.
  2. So I need the previous-smaller and next-smaller index for each bar — a monotonic increasing stack gives both in one pass.
  3. When popping, the popped bar's right boundary is the current index and its left boundary is the new stack top.
  4. Append a sentinel zero at the end so the stack fully drains.
Target complexity

O(n) time, O(n) space.

Pitfall

Forgetting the sentinel. Bars still on the stack at the end never get their area computed.

Say it out loud

“For each bar I need how far it extends before hitting something shorter on either side, and a monotonic stack gives both boundaries in one pass. The implementation detail that saves me is appending a zero-height sentinel, so everything drains off the stack and gets measured.”

Solve on LeetCode