The O(n) Club: Valid Parentheses — The Stack That Holds Your Code (and Life) Together

The O(n) Club: Valid Parentheses — The Stack That Holds Your Code (and Life) Together

⚡ TL;DR

You’re asked: Given a string of brackets (that’s (), [], and {}, not just your favorite kind), does everyone open and close in perfect order? Use a stack, don’t overthink it (that’s our job).

// Brute force? Oh, honey, don't. Here’s the painful way:
public boolean isValid(String s) {
    while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    }
    return s.isEmpty(); // O(n^2) — more drama, less results
}

🧠 How Devs Usually Mess This Up

Most folks hit every branch on the error tree:
– Assume it’s only ( and ). News flash: [, ] and {, } exist too.
– Pop from an empty stack because YOLO (hello, EmptyStackException).
– Think matching numbers = victory. Not if yours look like "([)]".
– See a balanced suffix and go “Ship it!” — forgetting a single misplaced bracket nukes the whole string.
– Treat the stack like an FYI instead of the main character in this soap opera.

🔍 What’s Actually Going On

Picture the stack as your favorite pile of coded dirty dishes: last dirty dish in, first clean dish out. Any clean-up job (a.k.a closing bracket) better match the latest dish, or your kitchen (a.k.a. code) gets condemned. Scan left to right:

🛠️ PseudoCode

• Create a Stack—Java’s version of “just put it on my tab”.

  Stack<Character> stack = new Stack<>();

• Loop over the string, char by char:
  • If it’s ‘(‘, ‘[‘, ‘{‘, push onto stack.
  • If it’s ‘)’, ‘]’, ‘}’, check:
    • Stack empty? Instant fail — nothing left to close.
    • Stack top does NOT match? Double fail — mismatched pair.
    • Otherwise, pop and continue on.
• End of string: stack should be empty. If not, some openers never got closure (like that one bug you never fixed).

💻 The Code

import java.util.Stack;
 public class ValidParentheses {
    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 opener = stack.pop();
                if (!matches(opener, c)) return false;
            }
        }
        return stack.isEmpty();
    }
    private boolean matches(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Stack underflow: No, your stack doesn’t hold imaginary numbers. Popping when empty = instant error, instant regret.
• Bracket bias: Only checking quantity, ignoring type/order. {[(])} isn’t valid, but looks nice.
• Leftovers: Anything left in the stack at the end? That’s a problem. Unless you collect open brackets for fun.
• Complexity check: O(n) time & space—if your string is ten million brackets long, get coffee first.

🧠 Interviewer Brain-Tattoo

“When nesting happens, bring a stack. Forget the stack, and your next job interview might include a pop quiz—pun very intended.”