Stack Fundamentals

🥞 Stacks: The Pancake Principle

The Big Idea

Imagine a stack of pancakes on a plate. You can only add a new pancake on top, and you can only take a pancake from the top. You can’t grab one from the middle—that would make the whole stack fall!

This is exactly how a Stack works in programming.

The rule is simple: Last In, First Out (LIFO). The last thing you put in is the first thing you take out.

🧠 Stack Fundamentals

What is a Stack?

A stack is like a pile of books, plates, or pancakes. You interact with it from one end only—the top.

The three magic words:

• Push = Add something to the top
• Pop = Remove something from the top
• Peek = Look at the top without removing it

Stack<String> pancakes = new Stack<>();

// Push pancakes onto stack
pancakes.push("Blueberry");
pancakes.push("Chocolate");
pancakes.push("Strawberry");

// Peek at top (Strawberry)
String top = pancakes.peek();

// Pop removes Strawberry
String eaten = pancakes.pop();

Real-Life Stacks

• Browser back button → Each page you visit is pushed. Back button pops the last one.
• Undo in Word → Each action is pushed. Ctrl+Z pops the last action.
• Call stack → When functions call other functions, they stack up!

graph TD
    A["Empty Stack"] --> B["Push: Blueberry"]
    B --> C["Push: Chocolate"]
    C --> D["Push: Strawberry"]
    D --> E["Pop: Strawberry removed"]
    E --> F["Top is now: Chocolate"]

🔐 Balanced Parentheses

The Problem

Given a string with brackets like (), [], {}, check if they’re balanced—every opening bracket has a matching closing bracket in the right order.

Think of it like this: Every time you open a door, you must close it. And you must close doors in reverse order—the last door you opened gets closed first!

The Stack Solution

1. See an opening bracket? Push it.
2. See a closing bracket? Pop and check if it matches.
3. Stack empty at the end? Balanced!

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    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();
}

Example:

• "{[]}" → Push {, push [, pop matches ], pop matches } ✅
• "([)]" → Push (, push [, pop [ but got ) ❌

📁 Simplify Path

The Problem

Unix file paths can be messy! Things like /a/./b/../../c/ need cleaning up.

The rules:

• . means current directory (ignore it)
• .. means go up one level (pop from stack)
• // multiple slashes are just one slash
• Everything else is a folder name (push it)

The Stack Solution

Split by /, then:

• Empty or .? Skip.
• ..? Pop if stack isn’t empty.
• Otherwise? Push the folder name.

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();
    String[] parts = path.split("/");

    for (String part : parts) {
        if (part.isEmpty() || part.equals(".")) {
            continue;
        } else if (part.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else {
            stack.push(part);
        }
    }

    return "/" + String.join("/", stack);
}

Example:

• /a/./b/../../c/ → Split: [a, ., b, .., .., c]
• Push a → Push b → Pop (for ..) → Pop (for ..) → Push c
• Result: /c

graph TD
    A["/a/./b/../../c/"] --> B["Split by /"]
    B --> C["a → Push"]
    C --> D[". → Skip"]
    D --> E["b → Push"]
    E --> F[".. → Pop b"]
    F --> G[".. → Pop a"]
    G --> H["c → Push"]
    H --> I["Result: /c"]

🏆 Longest Valid Parentheses

The Problem

Find the longest stretch of properly matched parentheses in a string.

Example: In "(()", the longest valid part is "()" = length 2.

The Stack Solution

The trick: Store indices, not characters!

1. Push -1 as a base (helps with counting).
2. For (: push its index.
3. For ): pop the stack.
   • If empty after pop: push current index as new base.
   • If not empty: current index minus stack top = valid length.

public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);  // Base for counting
    int maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);  // New base
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    return maxLen;
}

Example: ")()())"

• Index 0 ): Pop -1, empty, push 0
• Index 1 (: Push 1
• Index 2 ): Pop 1, length = 2-0 = 2
• Index 3 (: Push 3
• Index 4 ): Pop 3, length = 4-0 = 4 ✨
• Index 5 ): Pop 0, empty, push 5
• Answer: 4

🧹 Remove Invalid Parentheses

The Problem

Remove the minimum number of parentheses to make the string valid. Return all possible results.

Example: "()())()" → Remove one ) to get ["(())()", "()()()" ]

The Approach

Use BFS (Breadth-First Search) with a stack-based validity check:

1. Start with original string.
2. If valid, add to results.
3. If not, try removing each parenthesis one at a time.
4. Stop when we find valid strings (minimum removals).

public List<String> removeInvalidParentheses(String s) {
    List<String> result = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();

    queue.offer(s);
    visited.add(s);
    boolean found = false;

    while (!queue.isEmpty()) {
        String curr = queue.poll();

        if (isValid(curr)) {
            result.add(curr);
            found = true;
        }

        if (found) continue;

        for (int i = 0; i < curr.length(); i++) {
            char c = curr.charAt(i);
            if (c != '(' && c != ')') continue;

            String next = curr.substring(0, i)
                        + curr.substring(i + 1);
            if (!visited.contains(next)) {
                visited.add(next);
                queue.offer(next);
            }
        }
    }
    return result;
}

// Stack-based validity check
private boolean isValid(String s) {
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else if (c == ')') {
            if (count == 0) return false;
            count--;
        }
    }
    return count == 0;
}

➕ Minimum Add to Make Valid

The Problem

How many parentheses must you add to make the string valid?

Example: "(((" needs 3 ) → Answer: 3

The Simple Solution

Track unmatched opening and closing brackets:

public int minAddToMakeValid(String s) {
    int openNeeded = 0;   // Unmatched ')'
    int closeNeeded = 0;  // Unmatched '('

    for (char c : s.toCharArray()) {
        if (c == '(') {
            closeNeeded++;
        } else {
            if (closeNeeded > 0) {
                closeNeeded--;
            } else {
                openNeeded++;
            }
        }
    }

    return openNeeded + closeNeeded;
}

How it works:

• closeNeeded counts ( waiting for a )
• When we see ):
  • If there’s a waiting (, match them
  • Otherwise, we need an ( → increase openNeeded
• Total additions = unmatched ) + unmatched (

Examples:

• "(((" → closeNeeded = 3 → Add 3
• ")))" → openNeeded = 3 → Add 3
• "()" → All matched → Add 0
• "())(" → openNeeded = 1, closeNeeded = 1 → Add 2

🎯 The Golden Pattern

Every parentheses problem follows the same rhythm:

graph TD
    A["See Opening Bracket"] --> B["Push to Stack"]
    C["See Closing Bracket"] --> D{Stack Empty?}
    D -->|Yes| E["Invalid or Count It"]
    D -->|No| F["Pop and Check Match"]
    F --> G{Match?}
    G -->|Yes| H["Continue"]
    G -->|No| I["Handle Mismatch"]

Remember:

• Stack = Your memory of what’s still open
• Push = “I opened something, remember it”
• Pop = “I’m closing something, forget it”
• Empty stack at end = Everything matched!

🚀 Key Takeaways

You’ve got this! Stacks are your friend when anything needs to be “undone” in reverse order. Practice these patterns, and parentheses problems will feel like a breeze! 🌟