Valid Parentheses Problem Explained

Given a string of brackets, decide whether they are correctly matched and nested. The data structure is a stack, which most people reach for immediately. What separates a working solution from a nearly working one is that there are three ways a string can be invalid, and each needs its own check.

Written against Java 17.

The problem

"()"        -> true
"()[]{}"    -> true
"(]"        -> false     wrong closer
"([)]"      -> false     interleaved, not nested
"(("        -> false     never closed
"))"        -> false     closed without opening

The nesting requirement is what makes a counter insufficient. "([)]" has one of each bracket and equal opens and closes, and it is invalid, the order matters, and a count discards order.

The solution

static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char c : s.toCharArray()) {
        if (pairs.containsValue(c)) {
            stack.push(c);                       // an opener
        } else if (pairs.containsKey(c)) {
            // (1) a closer with nothing open, (2) a closer that does not match
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();                      // (3) anything left open
}

O(n) time and O(n) space, the stack holds at most every character, which is the case for a string of all openers. Map.of builds the closer-to-opener table once; declaring it static final outside the method is worth doing if this runs in a loop, since rebuilding a small immutable map per call is pure overhead.

The three checks

stack.isEmpty() before popping catches ")". Without it, pop() on an empty ArrayDeque throws NoSuchElementException, a crash rather than false, which in a service is a 500 instead of a validation error.

stack.pop() != pairs.get(c) catches "(]" and "([)]". The popped opener must be the partner of this closer; anything else means the brackets are interleaved rather than nested.

return stack.isEmpty() catches "((", the loop completes without error and the stack still holds two openers. Returning true here is the most common bug in this problem, because every test case with balanced counts passes.

Each check is one clause, and each corresponds to a distinct failure. A solution missing one is correct on roughly 80% of inputs.

Short-circuit ordering

if (stack.isEmpty() || stack.pop() != pairs.get(c))

The order is load-bearing. || short-circuits, so pop() runs only when the stack is non-empty. Reversing the operands calls pop() first and throws on ")".

That is a general property of this pattern worth naming: a guard and an action in one condition depends on evaluation order, so the guard must come first.

Why ArrayDeque and not Stack

Deque<Character> stack = new ArrayDeque<>();     // preferred
Stack<Character> legacy = new Stack<>();          // works, don't

java.util.Stack extends Vector, so every method is synchronised, a cost paid on every push in a single-threaded loop, and iterating it yields elements bottom-to-top rather than in pop order, which makes debugging output misleading. The Javadoc recommends Deque; see Java Stack for the full comparison.

Declare the variable as Deque, not ArrayDeque, the interface is the contract here as elsewhere.

Ignoring other characters

The solution above skips anything that is not a bracket, because neither branch matches. That is usually what a real validator wants, brackets inside a larger string:

"a(b[c]d)e"  -> true

If the problem states the input contains only brackets, an else return false is a reasonable strictness. Read the statement; both are defensible and they differ on the same input.

Tracing ”([)]”

char	action	stack (top first)
(	push	(
[	push	[ (
)	pop [, expected (	mismatch → false

Three characters in. Note that a counter-based solution reaches the end with a count of zero and returns true — the stack is what encodes the nesting.

Edge cases

• Empty string — the loop does not run and the empty stack returns true. That is the conventional answer, and it is worth confirming against the problem statement rather than assuming.
• A single character — "(" returns false via the final check, ")" via the first.
• Only openers — the final check catches them.
• Only closers — the first check catches them.
• Very long input — the stack grows to the input length in the worst case; there is no way around that, since the nesting depth is genuinely unbounded.

A variant worth working through

“Given a string with (, ) and *, where * can be an opener, a closer or nothing, is it balanceable?” The stack solution does not extend directly, because a * has three meanings and the choice cannot be made when it is read.

The trick is to track a range of possible open counts rather than one number:

static boolean checkValidString(String s) {
    int low = 0, high = 0;          // fewest and most possible unmatched openers

    for (char c : s.toCharArray()) {
        if (c == '(') { low++; high++; }
        else if (c == ')') { low--; high--; }
        else { low--; high++; }     // '*' — could reduce or increase

        if (high < 0) return false; // even treating every '*' as an opener, too many closers
        low = Math.max(low, 0);     // a negative low is not meaningful
    }
    return low == 0;                // some interpretation closes everything
}

O(n) time, O(1) space, and no stack. high < 0 is the early exit: if the maximum possible open count has gone negative, no assignment of the wildcards can rescue it. Clamping low at zero encodes that extra closers can always be absorbed by treating a * as empty.

Returning low == 0 rather than low <= 0 matters — the clamp already prevents a negative, so the distinction is between “some interpretation balances” and “always”. This is the same range-of-possibilities move that appears in interval and scheduling problems, and it is worth recognising as an alternative when a greedy single-value scan cannot commit.

The generalisation

The same stack shape solves a family of problems, and recognising it is worth more than the code:

• Expression evaluation — a stack of operands and a stack of operators, popping when precedence requires it.
• Removing the minimum number of invalid parentheses — the same scan, recording indices rather than returning early.
• The longest valid substring — push indices instead of characters, and the distance between the current position and the new top gives the length.
• Nested-structure parsing generally — JSON, XML and any language with balanced delimiters.

The property they share is that the most recent unmatched thing is the one that must be resolved first, which is precisely what a stack is for. When a problem statement contains the words “properly nested”, the answer is almost always a stack.

A counter suffices only when there is one bracket type, because with one type the order carries no information beyond the count staying non-negative:

static boolean isValidSingleType(String s) {
    int open = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') open++;
        else if (c == ')' && --open < 0) return false;
    }
    return open == 0;
}

O(1) space, and it breaks the moment a second bracket type appears.

More in the algorithms guides, and Java Stack for the data structure.

Frequently asked questions

Why is a stack the right structure?

The most recently opened bracket must be the first one closed, which is last-in-first-out by definition.

Why can’t I just count brackets?

A count discards order. "([)]" has balanced counts and is invalid because the brackets interleave rather than nest.

What are the three checks?

A closer arriving with an empty stack, a closer that does not match the top, and openers left on the stack when the input ends. Each catches a different invalid shape.

Which check do people forget?

The final stack.isEmpty(). Without it "((" returns true, and every balanced-count test case still passes.

Why does the order of the condition matter?

|| short-circuits, so the empty check must come before pop(). Reversed, an input of ")" throws instead of returning false.

Should I use Stack or ArrayDeque?

ArrayDeque, declared as Deque. Stack synchronises every call and iterates in the opposite order to popping.

What should an empty string return?

true by convention — it is vacuously balanced. Confirm against the problem statement.

What about characters that are not brackets?

The solution skips them, which suits validating brackets inside a larger string. Add an else return false if the input is specified as brackets only.

What is the space complexity?

O(n). A string of all openers puts every character on the stack, and the nesting depth is unbounded.

When is a counter enough?

With exactly one bracket type. Order then carries no information beyond the running count never going negative, and the space drops to O(1).