# O(n) Solution in Java

• Solution
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.

• Minor improvements :)

``````public boolean isValid(String s) {
Stack<Character> open = new Stack<>();
HashMap<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
for (char x : s.toCharArray()) {
if (map.containsKey(x)) {
open.push(x);
} else if (open.isEmpty() ||
map.get(open.pop()) != x) {
return false;
}
}
return open.isEmpty();
}
``````

• This post is deleted!

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