Stack / Monotonic Stack

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. Think of it like a stack of plates in a cafeteria: you add new plates to the top, and when you need a plate, you take from the top. The last plate you added is the first one you remove.

Real-World Analogies:

• •Stack of plates: add/remove only from the top
• •Browser back button: most recent page is accessed first
• •Undo functionality: most recent action is undone first
• •Function call stack: most recent function returns first

The LIFO Principle: Whatever you put in last comes out first. This is fundamentally different from a queue (FIFO - First-In, First-Out) where items come out in the order they went in.

This reversal property is extremely useful for many algorithmic problems.

A stack has a small set of fundamental operations, all running in O(1) constant time:

Why O(1)? All operations only touch the top of the stack. We never need to search or shift elements.

Visual Example:

Stacks are the right tool when your problem has one of these characteristics:

1. Matching Pairs When you need to match opening and closing elements:

• •Parentheses: (), [], {}
• •HTML/XML tags: <div>...</div>
• •Nested structures

2. Reverse Order Processing When the most recently added item must be processed first:

• •Undo operations
• •Browser history
• •Backtracking

3. Nested Structures When you encounter nested elements that must be processed inside-out:

• •Decode string: 3[a2[c]]
• •Calculator with parentheses
• •Recursive structures converted to iterative

4. "Next Greater/Smaller" Problems When finding the next element that satisfies a condition:

• •Daily temperatures (next warmer day)
• •Stock span problems
• •Largest rectangle in histogram

5. Expression Evaluation When evaluating mathematical expressions:

• •Infix to postfix conversion
• •Postfix (RPN) evaluation
• •Calculator problems

Recognition Signals in Problem Statements:

• •"Matching", "balanced", "valid parentheses"
• •"Next greater", "next smaller"
• •"Nested", "recursive structure"
• •"Evaluate expression"
• •"Most recent", "last added"

The most classic stack problem: determine if brackets are properly matched and nested.

The Key Insight: Valid parentheses follow LIFO order: the most recently opened bracket must be the first one closed. If we see {[, the next closing bracket MUST be ] (to close [), not } (to close {).

Algorithm:

1. •For each character in the string:
   • If opening bracket (, [, {: push onto stack
   • If closing bracket ), ], }:
     • Check if stack is empty (invalid if so)
     • Pop and verify it matches the closing bracket
2. •At the end: stack must be empty (all brackets closed)

Walkthrough: "([{}])"

Walkthrough: "([)]"

Edge Cases to Handle:

• •Empty string → valid
• •Only opening brackets "(((" → invalid (stack not empty)
• •Only closing brackets ")))" → invalid (pop from empty stack)
• •Single bracket → invalid

Here's a reusable template for all matching/balancing problems:

Template Structure:

Variations of This Pattern:

Extended Example: Track indices for removal

Watch how the stack grows with opening brackets and shrinks when matching closing brackets are found. Notice how the LIFO property ensures that inner brackets are always closed before outer ones.

A monotonic stack is a stack that maintains elements in sorted order (either always increasing or always decreasing from bottom to top). This powerful technique solves "next greater/smaller element" problems in O(n) time.

The Core Idea: Before pushing a new element, we pop all elements that would violate the monotonic property. When an element gets popped, we've found something about it (like its "next greater" element).

Two Types:

1. Monotonic Decreasing Stack (elements decrease bottom→top)

• •Pop when: current element > top of stack
• •Use for: "Next Greater Element" problems
• •Stack keeps: elements waiting for something greater

2. Monotonic Increasing Stack (elements increase bottom→top)

• •Pop when: current element < top of stack
• •Use for: "Next Smaller Element" problems
• •Stack keeps: elements waiting for something smaller

Visual: Decreasing Stack

When we popped 1 and 3, we learned that 4 is their "next greater element"!

Why O(n) Time? Each element is pushed exactly once and popped at most once. Even though there's a while loop inside the for loop, total operations across all iterations is at most 2n = O(n).

Problem: For each element in an array, find the next element to the right that is greater. If none exists, use -1.

Example: [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]

Why Monotonic Decreasing Stack? We keep elements "waiting" for a greater element. When a greater element arrives, all smaller elements on the stack have found their answer.

Algorithm:

1. •Initialize result array with -1 (default: no greater element)
2. •Use stack to store INDICES (not values)
3. •For each element:
   • While stack not empty AND current > stack top's value:
     • Pop index, set result[popped] = current
   • Push current index
4. •Elements remaining in stack have no next greater

Detailed Walkthrough: [2, 1, 2, 4, 3]

Key Insight: Store INDICES not values. This lets us:

1. •Update the result array at the correct position
2. •Calculate distances when needed (like Daily Temperatures)

See how elements wait on the monotonic decreasing stack until a larger element arrives. When a larger element comes, it "resolves" all smaller elements by becoming their next greater element.

Problem: Given daily temperatures, find how many days until a warmer day.

[73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]

This is Next Greater Element, but we return distance instead of value.

The Only Difference:

Walkthrough:

For "next smaller" problems, we flip the stack type:

Monotonic Increasing Stack:

• •Elements increase from bottom to top
• •Pop when: current < top of stack
• •Popped element has found its "next smaller"

Example: Find next smaller element for [4, 2, 5, 3, 1]

The Pattern Flip:

Problem: Find the largest rectangular area in a histogram.

Key Insight: For each bar, find how far left and right it can extend (until a shorter bar stops it). Then: area = height × width.

This is a "next smaller element" problem! A bar stops extending when it hits a shorter bar.

Algorithm:

1. •Use monotonic INCREASING stack (pop when current < top)
2. •When we pop a bar, we can calculate its area:
   • Height = the popped bar's height
   • Left boundary = new stack top (or start if empty)
   • Right boundary = current position
   • Width = right - left - 1
3. •Add a sentinel height 0 at the end to flush all bars

Walkthrough: [2, 1, 5, 6, 2, 3]

Why Width = i - stack.top - 1? The bar can extend from (stack.top + 1) to (i - 1), giving width = i - stack.top - 1. If stack is empty, the bar extends from 0 to i-1, giving width = i.

Watch how the monotonic increasing stack tracks bar boundaries. When a shorter bar arrives, taller bars get popped and their maximum possible rectangles are calculated.

Stacks excel at evaluating mathematical expressions because of operator precedence and nested parentheses.

The Challenge: In 3 + 2 * 4, we can't just compute left-to-right because * has higher precedence than +. We need to compute 2 * 4 first.

Stack Solution for Basic Calculator II: Process operators based on precedence:

• •* and /: High precedence → evaluate immediately
• •+ and -: Low precedence → defer (push to stack)

Algorithm:

1. •Track current number being built
2. •Track previous operator (starts as +)
3. •When we see a new operator or reach the end:
   • Apply the previous operator to current number
   • +: push number
   • -: push -number
   • *: pop, multiply, push result
   • /: pop, divide, push result
4. •Sum all values in stack

Walkthrough: "3+2*4-5"

Why Push -number for Subtraction? By converting a - b to a + (-b), we can sum the entire stack at the end without tracking signs separately.

When dealing with nested structures like 3[a2[c]], stacks help us save and restore state as we enter and exit nested levels.

Problem: Decode 3[a2[c]] → accaccacc

The Key Insight: When we see [, we're about to enter a nested level. We need to:

1. •Save current state (string so far, repeat count)
2. •Start fresh for the inner expression

When we see ], we:

1. •Restore outer state
2. •Combine: outer string + (inner string × count)

Algorithm:

1. •Maintain: current string, current number
2. •On [:
   • Push (current string, current number) to stacks
   • Reset both for inner expression
3. •On ]:
   • Pop count and previous string
   • current = previous + current.repeat(count)
4. •On digit: build number
5. •On letter: append to current string

Walkthrough: "3[a2[c]]"

Understanding related data structures helps you choose the right tool:

Queue (FIFO - First In, First Out)

• •Add to back, remove from front
• •Like a line at a store
• •Use for: BFS, level-order traversal, task scheduling

Deque (Double-Ended Queue)

• •Add/remove from both ends
• •Combines stack + queue capabilities
• •Use for: Sliding window maximum, palindrome checking

Comparison:

Implement Queue with Two Stacks: A classic interview problem! Use one stack for enqueue, one for dequeue.

Amortized O(1): Each element is moved at most once from inStack to outStack.

Quick Decision Tree:

Common Problem Patterns:

Mistake 1: Wrong Comparison Direction

Mistake 2: Forgetting Remaining Elements

Mistake 3: Storing Values Instead of Indices

Mistake 4: Empty Stack Check

Mistake 5: Integer Division in Calculator

Pro Tips:

1. •Sentinel values: Add dummy values to avoid edge cases (histogram adds 0 at end)
2. •Circular arrays: Iterate 2n times using i % n
3. •Debug: Print stack state at each step when confused
4. •Two stacks: When you need to track two things (count + string)

Time Complexity: O(n) for Monotonic Stack

Despite the nested while loop, monotonic stack is O(n) because:

• •Each element is pushed exactly ONCE
• •Each element is popped at most ONCE
• •Total operations across all iterations ≤ 2n

Space Complexity: O(n)

Worst case occurs with monotonically sorted input:

• •Decreasing stack + increasing input: all elements stay
• •Increasing stack + decreasing input: all elements stay

Operation Costs:

Language Notes:

• •JavaScript: Arrays work well; use .push(), .pop(), .at(-1)
• •Java: Use ArrayDeque, not legacy Stack class
• •Python: Lists work; use .append(), .pop(), [-1]
• •C++: Use std::stack or std::vector

When O(n) Isn't Enough: For problems requiring both next greater AND previous greater, you might run two passes or use a more complex approach, but each pass is still O(n).

For circular arrays (like Next Greater Element II), the last element wraps around to the first.

Problem: [1, 2, 1] → [2, -1, 2] (the last 1 sees the first 2)

Solution: Iterate 2n times, using i % n for the actual index.

Walkthrough: [1, 2, 1]