1. Valid Parentheses

Description

Valid Parentheses
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.
3. Every close bracket has a corresponding open bracket of the same type.

Approach 1

TC: O(n) SC: O(n)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> check = new Stack<>();
        HashMap<Character,Character> brackets = new HashMap<>();
 
        brackets.put(')','(');
        brackets.put('}','{');
        brackets.put(']','[');
 
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(brackets.containsKey(c)) {
                if(!check.isEmpty() && brackets.get(c).equals(check.peek())) {
                    check.pop();
                } else {
                    return false;
                }
            } else {
                check.push(c);
            }
        }
        return check.isEmpty();
    }
}

Approach 2

• Time: O(n) Space: O(n)

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0)
            return false;
 
        Stack<Character> brackets = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (brackets.isEmpty() && (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']'))
                return false;
            else if (s.charAt(i) == ')' && brackets.peek() == '(')
                brackets.pop();
            else if (s.charAt(i) == '}' && brackets.peek() == '{')
                brackets.pop();
            else if (s.charAt(i) == ']' && brackets.peek() == '[')
                brackets.pop();
            else
                brackets.add(s.charAt(i));
        }
 
        return brackets.isEmpty();
    }
}

---

Approach 1: Standard Stack with Bracket Matching

Intuition

A Stack (LIFO - Last In, First Out) naturally models nested brackets because the most recently opened bracket must be closed first.

Iterate through the string:

1. If you encounter an opening bracket ((, {, [), push it onto the stack.
2. If you encounter a closing bracket (), }, ]), check if the stack is non-empty and the top element is its matching opening bracket. If it matches, pop it. Otherwise, return false.
3. After the loop, the stack must be empty for the string to be valid.

import java.util.Stack;
 
class Solution {
    public boolean isValid(String s) {
        // Fast fail: an odd length string can never be balanced
        if (s.length() % 2 != 0) return false;
 
        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 != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
 
        return stack.isEmpty();
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass through string of length $N$.
• Space Complexity: $O(N)$ — In the worst case (e.g., "((((("), the stack stores up to $N$ characters.

---

Approach 2: “Push Expected Closing Bracket” Trick (Cleanest)

Intuition

Instead of pushing opening brackets and writing long conditional logic to check matching pairs later, push the expected closing bracket onto the stack.

When you encounter a closing bracket, simply check if stack.pop() == c. This eliminates the need for messy multi-branch if-else comparisons.

import java.util.Stack;
 
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
 
        Stack<Character> stack = new Stack<>();
 
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
 
        return stack.isEmpty();
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Inspects each character once.
• Space Complexity: $O(N)$ — Stack size up to $N/2$ elements for balanced strings.

---

Easy Memory Rule

“Push the expected closing bracket when you see an opening bracket. When you see a closing bracket, just pop() and compare directly.”