Master DSA: Stacks & Monotonic Patterns (L9)

This chapter explores the fundamental mechanics of the Stack data structure, its real-world applications, and its critical role in technical interviews. We will dissect how the Last-In, First-Out (LIFO) principle simplifies complex nested structures, trace call stacks in recursion, master the highly-requested Monotonic Stack pattern, and walk through step-by-step code implementations for classic FAANG problems.

1. Why Do We Need Stacks? (The LIFO Principle)

A Stack is a linear data structure that operates strictly on the LIFO (Last In, First Out) principle. This means the last element added to the stack is guaranteed to be the first one removed.

Unlike arrays or linked lists where elements can be accessed, inserted, or deleted at arbitrary indices, a stack restricts access to a single point: the top.

Real-Life Analogy: A Stack of Dinner Plates

Imagine a stack of dinner plates in a buffet.

• You place new plates on the very top of the pile (Push).
• When a guest needs a plate, they take the one from the very top (Pop).
• It is physically impossible (or highly risky!) to pull a plate directly from the middle or bottom without removing the ones above it first.

Core Stack Operations

2. Real-World Applications & System-Level Use Cases

Stacks are not just theoretical constructs; they form the backbone of many software systems and runtime environments.

A. Browser History Navigation

When you browse the web, your browser maintains your history using a stack.

• Every time you visit a new page, it is pushed onto the history stack.
• When you click the Back button, the browser pops the current page off the stack and displays the previous page (the new top of the stack).

B. Undo/Redo Functionality in Editors

Text editors (like VS Code or MS Word) track your keystrokes and formatting changes using an undo stack.

• Every action you take (typing a word, deleting a line) is pushed onto an undo stack.
• Pressing Ctrl + Z pops the last action off the stack and reverses its effects.

C. Expression Evaluation & Sign Resolution

Compilers use stacks to parse mathematical expressions (Infix, Prefix, and Postfix notations). A classic Google interview question involves resolving signs when opening nested brackets:

When the bracket opens, the negative sign outside must be applied to all internal elements, transforming the expression to $-a + b$. A stack is used to keep track of active signs as brackets nest deeper.

D. The Call Stack in Programming Languages

When a program executes nested function calls or recursion, the operating system maintains execution context using a Call Stack.

Vertical Call Stack Workflow

Consider a recursive function traversing a tree structure from node $1 \to 2 \to 3$:

3. When to Use a Stack (Mental Clues & Patterns)

Recognizing when a problem requires a stack is half the battle in an interview. Look for these specific clues in the problem description:

• Nested Structures: Parentheses (), HTML tags <div></div>, or nested directories.
• Tracking the Previous State / Backtracking: Problems requiring you to undo a step, revert to a previous state, or process elements in reverse order.
• Monotonic Relationships: Finding the "next greater," "next smaller," "previous greater," or "previous smaller" element in an array.
• Symmetric/Matching Pairs: Eliminating adjacent duplicates or matching opening/closing symbols.

Summary of Stack Patterns

4. Deep Dive into Monotonic Stacks

A Monotonic Stack is a specialized stack pattern where the elements inside the stack are kept in a strict sorted order (either increasing or decreasing) from bottom to top.

Monotonic Stack Variations

1. Decreasing Monotonic Stack

• Rule: Elements are stored from largest (bottom) to smallest (top).
• Action: Before pushing a new element $X$, pop all elements from the stack that are smaller than or equal to $X$.
• Primary Use Case: Finding the Next Greater Element or Previous Greater Element.

2. Increasing Monotonic Stack

• Rule: Elements are stored from smallest (bottom) to largest (top).
• Action: Before pushing a new element $X$, pop all elements from the stack that are greater than or equal to $X$.
• Primary Use Case: Finding the Next Smaller Element or Previous Smaller Element.

5. Step-by-Step Code Evolution: Valid Parentheses

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Intuition & Strategy

Instead of pushing opening brackets and checking them against closing brackets, we can use an elegant alternative: When encountering an opening bracket, push its corresponding closing bracket onto the stack.

When we encounter a closing bracket in the string, it must match the top of our stack. If it does not match, or if the stack is empty when we need to match, the string is invalid.

Step-by-Step Dry Run

For input string s = "()[]{}":

Java Implementation

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            // If we see an opening bracket, push its expected closing counterpart
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } 
            // If we see a closing bracket, check if it matches the top of the stack
            else {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        
        // If the stack is empty, all brackets were successfully matched
        return stack.isEmpty();
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ where $N$ is the length of the string. We perform a single pass over the string, and each stack operation (push, pop) takes $\mathcal{O}(1)$ time.
• Space Complexity: $\mathcal{O}(N)$ in the worst case (e.g., if the input string consists entirely of opening brackets like (((((((, we push all $N$ characters onto the stack).

6. Step-by-Step Code Evolution: Next Greater Element I

Problem Statement

You are given two integer arrays nums1 and nums2 where nums1 is a subset of nums2. Find all the next greater elements for nums1's elements in the corresponding places of nums2.

The next greater element of an element $x$ in nums2 is the first greater element to its right in nums2. If it does not exist, return $-1$ for this number.

Intuition & Strategy

A naive brute-force approach would use nested loops to search to the right of every element in nums2, resulting in an inefficient $\mathcal{O}(N^2)$ time complexity.

To optimize this to $\mathcal{O}(N)$, we use a Decreasing Monotonic Stack:

1. We traverse nums2 from left to right.
2. While the stack is not empty and the current element num is greater than the element at the top of our stack (stack.peek()), it means num is the next greater element for the stack's top element.
3. We pop the top element from the stack and record this relationship in a hash map: map.put(poppedElement, num).
4. We push the current element num onto the stack.
5. Any elements remaining in the stack at the end of the traversal do not have a next greater element, so their value defaults to $-1$.
6. Finally, we map the precomputed results from our hash map back to nums1.

Step-by-Step Dry Run

For nums2 = [1, 3, 4, 2]:

Java Implementation

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        
        // Step 1: Find next greater elements for all numbers in nums2
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }
        
        // Step 2: Remaining elements in stack have no next greater element
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }
        
        // Step 3: Build the result array for nums1
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.get(nums1[i]);
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N + M)$ where $N$ is the length of nums2 and $M$ is the length of nums1. Each element in nums2 is pushed and popped from the stack exactly once, making the monotonic stack phase $\mathcal{O}(N)$. Mapping the results for nums1 takes $\mathcal{O}(M)$ time.
• Space Complexity: $\mathcal{O}(N)$ to store the hash map and stack containing elements of nums2.

7. Step-by-Step Code Evolution: Simplify Path

Problem Statement

Given an absolute path for a Unix-style file system (starting with a slash '/'), convert it to the simplified canonical path.

In a Unix-style file system:

• A single period '.' refers to the current directory.
• A double period '..' moves the directory up a level (to the parent directory).
• Multiple consecutive slashes (e.g., //) are treated as a single slash /.

The canonical path must:

1. Start with a single slash /.
2. Have directories separated by a single slash /.
3. Not end with a trailing /.
4. Only contain the directories on the path from the root directory to the target (no . or ..).

Intuition & Strategy

1. Split the input path string using the slash / as a delimiter. This breaks the path down into individual components (tokens).
2. Iterate through each token:
   • If the token is empty or . (current directory), ignore it.
   • If the token is .. (parent directory), pop the top directory off our stack (if the stack is not empty).
   • For any other valid directory name, push it onto the stack.
3. Reconstruct the canonical path by joining the elements in the stack from bottom to top, separated by /.

Note on Stack Traversal Order: Standard stack popping retrieves elements in reverse order (LIFO). However, when reconstructing a directory path, we need the elements in insertion order (FIFO). In Java, iterating over a Stack using a for-each loop (for (String dir : stack)) traverses the elements from bottom to top (insertion order), which is exactly what we need to rebuild the path.

Java Implementation

import java.util.Stack;

public class SimplifyPath {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        
        // Split the path by '/'
        String[] components = path.split("/");
        
        for (String component : components) {
            // Ignore empty tokens (caused by multiple slashes "//") or single dots "."
            if (component.isEmpty() || component.equals(".")) {
                continue;
            }
            // If "..", go up one directory level by popping from stack
            else if (component.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } 
            // Otherwise, it's a valid directory name
            else {
                stack.push(component);
            }
        }
        
        // If the stack is empty, we are at the root directory "/"
        if (stack.isEmpty()) {
            return "/";
        }
        
        // Reconstruct the path from bottom to top
        StringBuilder result = new StringBuilder();
        for (String dir : stack) {
            result.append("/").append(dir);
        }
        
        return result.toString();
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ where $N$ is the length of the path string. Splitting the string takes $\mathcal{O}(N)$ time, and we process each token in a single pass.
• Space Complexity: $\mathcal{O}(N)$ to store the split path components and the stack elements.

8. Summary and Key Takeaways

• LIFO Core: The stack is a linear data structure governed by the Last-In, First-Out principle. All operations (push, pop, peek, isEmpty) run in $\mathcal{O}(1)$ constant time.
• Nested Structure Resolution: Stacks are the default data structure for processing nested structures, matching pairs (such as parentheses), and parsing mathematical expressions.
• System Call Simulation: The runtime call stack manages function execution and recursion. You can convert any recursive algorithm into an iterative one by managing a stack manually.
• Monotonic Stack Pattern: This pattern is used to find the next/previous greater/smaller element in linear $\mathcal{O}(N)$ time.
• Decreasing Monotonic Stack: Keeps elements sorted from largest to smallest to find the Next Greater Element.
• Increasing Monotonic Stack: Keeps elements sorted from smallest to largest to find the Next Smaller Element.
• Path Parsing: Splitting a string into tokens and processing them with a stack is a highly effective design pattern for directory traversal and command history simulation.