Valid Parentheses

EasyStack · Bracket Matching🧩 Stack LeetCode #20 ↗Updated Oct 30, 2026

Problem

A string s contains only the bracket characters ( ) [ ] { }. Decide whether it is well-formed: every opening bracket is closed by a bracket of the same type, and brackets close in the reverse order they were opened (properly nested).

Input"([]{})"Outputtrue

Input"(]"Outputfalse

Input"([)]"Outputfalse

1 ≤ s.length ≤ 10⁴ · s consists only of ()[]{}

Try it yourself

Java

class Solution {
    public boolean isValid(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The bracket that must close next is always the most recently opened one that is still open — last in, first out, i.e. a stack.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceRepeatedly Delete Adjacent Pairs

Time O(n²)Space O(n)

Any valid string contains an innermost pair (), [] or {} side by side. Delete all such pairs and repeat until nothing changes; the string was valid iff it shrinks to empty.

Java

public boolean isValid(String s) {
    String prev;
    do {
        prev = s;
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    } while (!s.equals(prev));
    return s.isEmpty();
}

Cute and short, but up to n/2 rounds of O(n) string rebuilding.

BetterStack + Closer→Opener Map

Time O(n)Space O(n)

Push every opening bracket. On a closing bracket, the stack top must be its partner (looked up in a map); otherwise fail. At the end the stack must be empty, or some bracket was never closed.

Java

public boolean isValid(String s) {
    Map<Character, Character> open = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!open.containsKey(c)) stack.push(c);            // opening bracket
        else if (stack.isEmpty() || !open.get(c).equals(stack.pop())) return false;
    }
    return stack.isEmpty();
}

Linear and clear; boxing Characters and map lookups add overhead.

OptimalArray Stack of Expected Closers

Time O(n)Space O(n)

On an opener, push the closer we expect; then a closing char just has to equal the popped value — no map needed. A primitive char[] stack avoids boxing, and an odd length is rejected instantly.

Java

public boolean isValid(String s) {
    if (s.length() % 2 == 1) return false;
    char[] stack = new char[s.length()];
    int top = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') stack[top++] = ')';       // push expected closer
        else if (c == '[') stack[top++] = ']';
        else if (c == '{') stack[top++] = '}';
        else if (top == 0 || stack[--top] != c) return false;
    }
    return top == 0;
}

Dry run"([]{})"

i index changed

i=0
(
i
[

]

{

}

)

push ) → stack: )
i=1
(

[
i
]

{

}

)

push ] → stack: ) ]
i=2
(

[

]
i
{

}

)

pop ] matches → stack: )
i=3
(

[

]

{
i
}

)

push } → stack: ) }
i=4
(

[

]

{

}
i
)

pop } matches → stack: )
i=5
(

[

]

{

}

)
i
pop ) matches, empty ✔

Same Big-O, but single pass with no allocations per char — fastest in practice.

Pro tip

Same pattern validates HTML/XML tags: push the expected closing tag and compare on each close.

At a glance

Level	Approach	Time	Space
Brute Force	Repeatedly Delete Adjacent Pairs	`O(n²)`	`O(n)`
Better	Stack + Closer→Opener Map	`O(n)`	`O(n)`
Optimal	Array Stack of Expected Closers	`O(n)`	`O(n)`

Common pitfalls

Only counting brackets — "([)]" has balanced counts but is invalid.
Popping an empty stack on a leading closer like ")".
Returning true without checking the stack is empty — "((" fails.

Interview tips

Explain why LIFO matches nesting: the last opened must be the first closed.
Mention the odd-length early exit as a free optimisation.
Compare two Character objects with equals, never !=.

Pattern

Stack for nested matching → brackets, tags, or any open/close pairs that must nest.

My notes saved in this browser