Session-05-Stack

Practice Session 5: Stack & Monotonic Stack

Overview

Stacks are the right tool whenever the problem requires the most recently seen unresolved item — parenthesis matching, undo history, function call frames. Monotonic stacks add a stricter invariant: they keep elements in sorted order by popping everything that violates the order before each push. This lets every “next greater/smaller” or “maximum spanning rectangle” problem be solved in O(n) time with each element pushed and popped exactly once. At senior level the key skill is recognising which flavour — regular stack, monotonic decreasing, or monotonic increasing — and explaining the amortised cost argument confidently.

---

Problem 1: Valid Parentheses

Link: LeetCode 20

Quick Summary: Given a string containing only ()[]{}, return true if every open bracket is closed by the correct bracket type in the correct order.

Industry Context: Every IDE does this in real time (syntax highlighting, red-squiggle on unmatched braces). HTML/XML parsers use the identical algorithm to validate nesting of tags. Compiler front-ends use it as a pre-parse step before building an AST.

Approach 1: Brute Force — Repeated Collapse

// O(n²) time  O(n) space
public static boolean isValidBrute(String s) {
    StringBuilder sb = new StringBuilder(s);
    boolean changed = true;
    while (changed) {
        changed = false;
        int i = 0;
        while (i < sb.length() - 1) {
            char l = sb.charAt(i), r = sb.charAt(i + 1);
            if ((l == '(' && r == ')') ||
                (l == '[' && r == ']') ||
                (l == '{' && r == '}')) {
                sb.delete(i, i + 2);
                changed = true;
            } else {
                i++;
            }
        }
    }
    return sb.length() == 0;
}

• Time: O(n²) — each pass is O(n) and there can be n/2 passes
• Space: O(n) for the StringBuilder copy
• Tradeoff: Conceptually clear but catastrophically slow; never use in production code paths called at parse time

Approach 2: Optimal — Single-Pass Stack

// O(n) time  O(n) space
public static boolean isValidOptimal(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

• Time: O(n) — single pass, each character touched once
• Space: O(n) worst case (all open brackets before any close)
• Key Insight: A closing bracket must pair with the most recently seen unmatched open bracket. “Most recently seen unmatched” is the definition of a stack top. The stack isEmpty() check at end handles the case where unmatched open brackets remain.

---

Problem 2: Min Stack

Link: LeetCode 155

Quick Summary: Design a stack that supports push, pop, top, and getMin() all in O(1) time.

Industry Context: Database transaction systems maintain a min-cost undo log alongside the main write-ahead log; getMin() is equivalent to “cheapest rollback point”. Monitoring systems that need the running floor of a metric window (e.g., minimum latency over the last N operations) use this exact abstraction.

Approach 1: Two-Stack Design

// All operations O(1) time  O(n) space (2n entries)
static class MinStackTwoStack {
    private final Deque<Integer> data    = new ArrayDeque<>();
    private final Deque<Integer> minTrack = new ArrayDeque<>();
 
    public void push(int val) {
        data.push(val);
        int newMin = minTrack.isEmpty() ? val : Math.min(val, minTrack.peek());
        minTrack.push(newMin);
    }
 
    public void pop()    { data.pop(); minTrack.pop(); }
    public int  top()    { return data.peek(); }
    public int  getMin() { return minTrack.peek(); }
}

• Time: O(1) all operations
• Space: O(2n) — the min-track stack mirrors every push
• Tradeoff: Very readable; the constant-factor memory overhead is acceptable unless the stack holds extremely large objects

Approach 2: Single-Stack Encoding Trick

// All operations O(1) time  O(n) space — ~half entries vs Approach 1
static class MinStackEncoding {
    private final Deque<Long> stack = new ArrayDeque<>();
    private long min;
 
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = val;
        } else {
            stack.push((long) val - min); // store delta, not raw value
            if (val < min) min = val;
        }
    }
 
    public void pop() {
        long top = stack.pop();
        if (top < 0) min = min - top; // top == val - old_min  =>  old_min recoverable
    }
 
    public int top() {
        long top = stack.peek();
        return top < 0 ? (int) min : (int)(top + min);
    }
 
    public int getMin() { return (int) min; }
}

• Time: O(1) all operations
• Space: O(n) — one stack, one scalar
• Key Insight: Store val − currentMin instead of val. A negative delta means val itself was a new minimum; the old minimum can be recovered on pop as min − delta. Using long avoids integer overflow in the subtraction. This is the same idea as “store differences, not absolutes” used in delta encoding and time-series compression.

---

Problem 3: Daily Temperatures

Link: LeetCode 739

Quick Summary: Given a list of daily temperatures, return an array where result[i] is the number of days until a warmer temperature; 0 if no such day exists.

Industry Context: Temperature alerting in time-series monitoring systems (e.g., “how many minutes until CPU temperature drops below threshold again?”). Stock technical analysis uses this exact pattern for computing “days until next higher close”. Latency SLO dashboards: “how many requests must we serve before the next one that beats our P99 target?”

Approach 1: Brute Force — Linear Scan Per Day

// O(n²) time  O(1) space excluding output
public static int[] dailyTemperaturesBrute(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (temperatures[j] > temperatures[i]) {
                result[i] = j - i;
                break;
            }
        }
    }
    return result;
}

• Time: O(n²) — inner loop is O(n) per day
• Space: O(1) excluding output array
• Tradeoff: Works correctly but fails for large inputs (n = 10⁵ → ~10¹⁰ operations)

Approach 2: Optimal — Monotonic Decreasing Stack

// O(n) time  O(n) space
public static int[] dailyTemperaturesOptimal(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // indices, decreasing temp order
 
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

• Time: O(n) — each index pushed once, popped at most once
• Space: O(n) for the stack
• Key Insight: Maintain a stack of days whose “next warmer day” is still unresolved, in decreasing temperature order. The moment a warmer day arrives it resolves all consecutive days on the stack top in O(1) amortised per element. Storing indices (not temperatures) lets us compute the distance directly.

---

Problem 4: Largest Rectangle in Histogram

Link: LeetCode 84

Quick Summary: Given an array of bar heights, find the area of the largest rectangle that fits entirely within the histogram.

Industry Context: 2D bin-packing in warehouse/logistics systems (largest contiguous floor slot for a pallet). Skyline rendering in mapping/GIS software: computing the maximal unobstructed viewport. In databases, histogram-based query cost estimation uses this to compute worst-case join cardinality windows.

Approach 1: Brute Force — All Pairs

// O(n²) time  O(1) space
public static int largestRectangleBrute(int[] heights) {
    int n = heights.length;
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int minHeight = heights[i];
        for (int j = i; j < n; j++) {
            minHeight = Math.min(minHeight, heights[j]);
            maxArea = Math.max(maxArea, minHeight * (j - i + 1));
        }
    }
    return maxArea;
}

• Time: O(n²)
• Space: O(1)
• Tradeoff: Straightforward but too slow; breaks at n = 10⁵

Approach 2: Optimal — Monotonic Increasing Stack

// O(n) time  O(n) space
public static int largestRectangleOptimal(int[] heights) {
    int n = heights.length;
    int maxArea = 0;
    Deque<Integer> stack = new ArrayDeque<>(); // indices, increasing height order
 
    for (int i = 0; i <= n; i++) {         // i == n is the sentinel flush
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width  = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea    = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

• Time: O(n) — each bar pushed/popped at most once
• Space: O(n)
• Key Insight: An increasing stack means each bar extends leftward as far as the bar immediately below it on the stack (the nearest shorter bar to its left). When a shorter bar arrives on the right, that determines the right boundary. The width is therefore i − stack.peek() − 1 after popping. A sentinel 0-height bar at position n forces all remaining bars to be processed without a special post-loop pass.

---

Problem 5: Online Stock Span

Link: LeetCode 901

Quick Summary: For each new stock price, compute the span — the number of consecutive days (including today) for which the price was ≤ today’s price.

Industry Context: Real-time financial dashboards computing price dominance windows (candlestick patterns, moving-high indicators). Network congestion monitoring: “how many consecutive measurement intervals has throughput been below this threshold?” DevOps runbooks: “how many consecutive deploys have had error rates at or below today’s level?”

Approach 1: Brute Force — Linear Scan Per Price

// O(n) per call  O(n) total space
static class StockSpannerBrute {
    private final List<Integer> prices = new ArrayList<>();
 
    public int next(int price) {
        prices.add(price);
        int span = 1;
        for (int i = prices.size() - 2; i >= 0; i--) {
            if (prices.get(i) <= price) span++;
            else break;
        }
        return span;
    }
}

• Time: O(n) per next() call, O(n²) total for n calls
• Space: O(n)
• Tradeoff: Correct but degenerates badly on monotonically increasing price sequences (the worst case for scanning)

Approach 2: Optimal — Monotonic Decreasing Stack with Accumulated Span

// O(1) amortised per call  O(n) space
static class StockSpannerOptimal {
    private final Deque<int[]> stack = new ArrayDeque<>(); // [price, span]
 
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];   // absorb the collapsed range's span
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

• Time: O(1) amortised — each price pushed once, popped once across all calls
• Space: O(n)
• Key Insight: Storing the accumulated span alongside each price collapses previously resolved ranges in a single pop, analogous to path compression in Union-Find. When today’s price dominates a run of past prices, we don’t re-examine each day individually; we absorb the entire already-computed span of the stack top. This is the difference between O(n²) and O(n) total work.

---

Key Takeaways

Pattern Recognition Triggers

• “Matching/balancing” or “valid nesting” → regular stack (push open, verify on close)
• “Next greater / next smaller element” → monotonic stack (decreasing for next-greater, increasing for next-smaller)
• “Largest rectangle / maximum area / span” → monotonic increasing stack (track left boundary implicitly)
• “Running minimum/maximum alongside push/pop” → min-stack (two-stack or delta encoding)
• “How long has condition X been continuously satisfied?” → monotonic stack with accumulated count

Monotonic Stack vs Regular Stack

Situation	Use
Need LIFO order only, no ordering between elements	Regular stack
”Next element that breaks a trend”	Monotonic stack
Each element needs to know about its nearest dominating neighbour	Monotonic stack
Answer depends on the span of a contiguous run	Monotonic stack with accumulated span
O(1) per-query min/max alongside stack operations	Min/Max stack (two-stack or encoding)

Amortised O(n) Argument — Say This in Interviews

The classic concern is the nested while loop inside an outer for loop. The counter-argument: across the entire algorithm, each of the n elements is pushed at most once and popped at most once — so the total number of push + pop operations is bounded by 2n regardless of the input. This is the standard aggregate amortised analysis; it is exactly what you should state when an interviewer asks “isn’t that O(n²)?”.

Common Pitfalls

• Forgetting the sentinel (zero-height bar) for histogram — without it, bars never popped from the stack by the loop remain unprocessed
• Using Stack<> (Java legacy) instead of ArrayDeque — ArrayDeque is faster and the preferred implementation since Java 6
• Off-by-one in width calculation for histogram: width is i − stack.peek() − 1, not i − stack.peek()
• Integer overflow in Min Stack encoding — always use long for the delta subtraction before comparing to int bounds
• Not handling the empty-stack check before stack.pop() in parentheses matching (the ) with empty stack case)

Connections to System Design

Stack Pattern	System Design Analogue
Valid Parentheses	XML/JSON parser validation layer; HTML sanitizer in a content pipeline
Min Stack	Cheap-rollback pointer in a write-ahead log; sliding-window floor in a metrics store
Daily Temperatures / Stock Span	Alerting engines that compute “time until next threshold crossing”; candlestick pattern detectors in trading systems
Largest Rectangle	Bin-packing allocator; maximum contiguous free-memory region in a slab allocator
Monotonic stack (general)	Undo/redo buffer compaction; event-stream aggregation where dominated events can be discarded

Stack in Language Runtime Design

The call stack itself is a hardware/OS-level stack. Understanding stack overflow (unbounded recursion), tail-call elimination (compiler converts recursion to iteration, collapsing the stack), and stack frame layout is directly relevant to JVM tuning (-Xss), Go goroutine stacks (dynamically resizable), and async/await desugaring (continuations replace explicit stack frames with heap-allocated state machines).