O(n) Solution in Java

  • 0

    By implementing a simple stack the problem can be solved in a single pass. As we iterate over the characters in the string we push the opposite bracket onto the stack to allow for a simplified checking process when it comes time to pop values off.

    After iterating through all values we return a function that will be true if our stack is empty meaning all parenthesis have been closed or false if there's still parenthesis left over.

    class Solution {
        public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<Character>(); 
            for (char c : s.toCharArray()){ 
                if (c == '(') stack.push(')');
                else if (c == '{') stack.push('}');
                else if (c == '[') stack.push(']');
                else if (stack.peek() == null || stack.pop() != c) return false;
            return stack.isEmpty();

    Complexity Analysis

    • Time Complexity: O(n) We traverse the string containing n characters only once, and each stack operation costs only O(1) time.
    • Space Complexity: O(n) The extra space will depend on the number of unmatched parenthesis stored in the stack at once. In a worst case scenario this will be n elements.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.