Valid Parentheses

easyStack48 stepsJava · Python · C++

Check that every bracket is closed by the same type in the right order. Push opening brackets; on a closing bracket the top of the stack must be its partner. The string is valid only if the stack ends empty.

▶ Watch the animated trace

Traced input: s = "{[()]}()" → true. Original problem: neetcode.io/problems/validate-parentheses

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(n)

Best case is an immediate mismatch. The stack can hold n/2 brackets.

Key idea

The most recent unclosed bracket must be closed first: last in, first out.
On ), ], }, pop and check it matches.
A closing bracket with an empty stack is invalid.
Leftover openers at the end are invalid too.

Common mistakes

Only counting brackets misses order errors like "([)]".
Popping an empty stack throws; check isEmpty() first.
Forgetting the final isEmpty() check ("((" would pass).

Solution

Java

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
            continue;
        }
        char open = c == ')' ? '(' : c == ']' ? '[' : '{';
        if (stack.isEmpty() || stack.peek() != open) {
            return false;
        }
        stack.pop();
    }
    return stack.isEmpty();
}

Python

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
            continue
        if not stack or stack[-1] != pairs[c]:
            return False
        stack.pop()
    return not stack

C++

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
            continue;
        }
        char open = c == ')' ? '(' : c == ']' ? '[' : '{';
        if (st.empty() || st.top() != open) {
            return false;
        }
        st.pop();
    }
    return st.empty();
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Wrong order The `)` meets `[` on top of the stack.	`s = "([)]"`	`false`
Only openers The stack isn't empty at the end.	`s = "(("`	`false`
Starts with a closer Nothing to match against.	`s = "]"`	`false`
Empty string No brackets, nothing unbalanced.	`s = ""`	`true`
Simple pairs Each pair opens and closes immediately.	`s = "()[]{}"`	`true`