Parenthesis Checker

Time: O(n)

Space: O(n)

Intuition

Use a stack. Push opening brackets. For closing brackets, check the stack top is the matching opener. Return true iff the stack is empty at the end.

Algorithm

1For each char: if open bracket ({,[,(): push. If close: if stack empty or top doesn't match: return false; pop.
2Return stack.isEmpty().

Example Walkthrough

Input: "{()[{()}]}"

1.{ push. ( push. ) matches ( â†’ pop. [ push. { push. ( push. ) â†’ pop. } â†’ pop. ] â†’ pop. } â†’ pop. Stack empty â†’ true.

Output: true

Common Pitfalls

•Check stack is non-empty before comparing top â€” an extra closing bracket crashes a stack-empty check.

Parenthesis Checker.java

Java

// Approach: Stack-based. Push open brackets; on close bracket check stack top matches.
// Time: O(n) Space: O(n)
class Solution {
    static boolean isBalanced(String s) {
        Stack<Character> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt((i));

            if (ch == '(' || ch == '{' || ch == '[')
                st.push(ch);

            else if (!st.isEmpty() && st.peek() == '(' && ch == ')')
                st.pop();
            else if (!st.isEmpty() && st.peek() == '{' && ch == '}')
                st.pop();
            else if (!st.isEmpty() && st.peek() == '[' && ch == ']')
                st.pop();
            else
                st.push(ch);
        }

        return st.isEmpty();
    }
}

Was this solution helpful?