20. Valid Parentheses

Intuition

We need to ensure that every opening bracket has a matching closing bracket of the same type and in the correct order. A stack is ideal for tracking the most recent unclosed opening bracket.

Complexity

Space Complexity	Time Complexity
$\text{O}(n)$	$\text{O}(n)$

Code

public boolean isValid(String input) {
    Stack<Character> bracketStack = new Stack<>();

    for (int index = 0; index < input.length(); ++index) {
        char currentChar = input.charAt(index);

        // Check for mismatched or unbalanced closing brackets
        if (currentChar == ')' && (bracketStack.isEmpty() || bracketStack.peek() != '(')) return false;
        else if (currentChar == '}' && (bracketStack.isEmpty() || bracketStack.peek() != '{')) return false;
        else if (currentChar == ']' && (bracketStack.isEmpty() || bracketStack.peek() != '[')) return false;

        // Pop matched closing brackets
        else if (currentChar == ')' || currentChar == ']' || currentChar == '}') bracketStack.pop();
        
        // Push opening brackets
        else bracketStack.push(currentChar);
    }

    // Valid if no unmatched opening brackets remain
    return bracketStack.isEmpty();
}