Valid Parentheses – Explained with Stack & Visualization

Difficulty: Easy
Topics: Strings, Stack, Algorithms

🧠 Problem Understanding (In Simple Words)

We are given a string that contains only brackets like:

• Round: ()
• Curly: {}
• Square: []

Our goal is to check:

👉 Is this bracket sequence properly balanced and correctly ordered?

💡 Intuition (Very Important)

Think of brackets like opening and closing doors:

• When you see an opening bracket → you "open a door"
• When you see a closing bracket → you must "close the most recently opened door"

👉 This is exactly why we use a Stack (LIFO - Last In First Out)

🧩 Why Stack Works Here

• The last opened bracket must be closed first
• Stack helps us track this order efficiently

Example:

Input: "([])"

Step-by-step:
Push '('
Push '['
Now ']' → matches '[' → pop
Now ')' → matches '(' → pop

Stack becomes empty → ✅ Valid

🚀 Approach (Step-by-Step)

1. Create an empty stack
2. Traverse each character in the string:
   • If it's an opening bracket → push to stack
   • If it's a closing bracket:
     • Check if stack is empty → invalid
     • Check top of stack:
       • If it matches → pop
       • Else → invalid
3. After traversal:
   • If stack is empty → valid
   • Else → invalid

🎯 Visualization Using DrawToCode

This problem becomes much easier when visualized:

• Each push → new element added visually
• Each pop → element removed
• You can see the stack changing step-by-step

👉 Using DrawToCode, you can:

• Track how brackets are pushed and popped
• Understand why incorrect sequences fail
• Debug your logic visually

💻 Code (Java Example)

import java.util.*;

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

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;

                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

⏱️ Complexity Analysis

• Time Complexity: O(n) → we traverse the string once
• Space Complexity: O(n) → stack can store all opening brackets

🔍 Example Walkthrough

Input:

s = "(]"

Execution:

• Push '('
• Next ']' → expected '[' but found '(' ❌

👉 Output: false

Input:

s = "()[]{}"

Execution:

• Push '(' → pop ')'
• Push '[' → pop ']'
• Push '{' → pop '}'

👉 Stack becomes empty → ✅ true

🧪 Edge Cases to Consider

• Empty string → valid
• Only opening brackets → invalid
• Only closing brackets → invalid

🏁 Final Thought

This is a classic problem to understand:

• Stack behavior
• Order-based validation
• Real interview logic

👉 Once you visualize it, the concept becomes very easy to grasp