Free lesson · DSA Mastery - Interview Prep, End to End

Valid Parentheses

Medium6 min readdsastacks

Valid Parentheses

Valid Parentheses is the canonical stack problem - the one that defines the entire standard family. Given a string of brackets (), [], {}, decide whether they're properly balanced and nested: every opener has a matching closer of the same type, and they close in the correct order. The solution is the purest expression of "push openers, pop and match on closers" you'll ever write. We present the standard stack approach plus a naive string-reduction baseline for contrast.

The single insight: a closing bracket must match the most recently opened, still-unclosed bracket - which is exactly LIFO. The stack remembers the openers in the order they appeared, and each closer reconciles against the top.

The Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input:  s = "()"
Output: true

Example 2:

Input:  s = "()[]{}"
Output: true

Example 3:

Input:  s = "(]"
Output: false

Example 4:

Input:  s = "([)]"
Output: false  (wrong order: ] closes before ) )

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Approaches Overview

The stack approach is the textbook answer: one pass, pushing openers and matching each closer against the top. The reduction approach (repeatedly delete matched pairs) is intuitive but quadratic.

Approach 1: Repeated String Reduction

The Idea

Repeatedly scan the string and remove any adjacent matched pair ((), [], {}). If the string eventually becomes empty, it was valid; if a full scan removes nothing and the string is non-empty, it's invalid. Each removal can shift the rest, and you may need many passes - O(n²).

Logic Flowchart

graph TD
    A["while string changes"] --> B["remove all of (), [], {} pairs"]
    B --> C{"string empty?"}
    C -->|Yes| D["Return true"]
    C -->|No| E{"any removal this pass?"}
    E -->|Yes| A
    E -->|No| F["Return false"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows the reduction approach. We repeatedly delete every adjacent matched pair until the string stops changing. An empty string means valid; a non-empty string with no removals means invalid. Repeated rescans make it quadratic.

Code

public static boolean isValidReduction(String s) {
    int prevLen;
    do {
        prevLen = s.length();
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    } while (s.length() != prevLen);
    return s.isEmpty();
}

This Java code repeatedly removes matched bracket pairs until the string stops shrinking, then returns whether it is empty. Each pass rescans the whole string, giving quadratic time.

Complexity

Time: O(n²) - repeated scans and string rebuilds. Space: O(n).

The stack does it in one pass.

Approach 2: Stack of Openers - Optimal

The Idea

Scan left to right. When you see an opener, push it. When you see a closer, the top of the stack must be the matching opener - if the stack is empty or the top doesn't match, the string is invalid. Pop the matched opener and continue. At the end, the stack must be empty (no unclosed openers remain). A small map from closer to its opener keeps the matching clean.

Logic Flowchart

graph TD
    A["stack empty; scan each char c"] --> B{"c is opener?"}
    B -->|Yes| C["push c"]
    B -->|No| D{"stack empty OR top != match(c)?"}
    D -->|Yes| E["Return false"]
    D -->|No| F["pop"]
    C --> G{"more chars?"}
    F --> G
    G -->|Yes| A
    G -->|No| H{"stack empty?"}
    H -->|Yes| I["Return true"]
    H -->|No| J["Return false"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows the stack approach. We push each opener. On a closer, if the stack is empty or its top is not the matching opener, the string is invalid; otherwise we pop. After the scan, an empty stack means valid.

Code

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

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);                                  // opener
        } else {
            if (stack.isEmpty() || stack.pop() != match.get(c))
                return false;                               // mismatch or nothing to match
        }
    }
    return stack.isEmpty();                                 // no unclosed openers
}

// Usage:
// isValid("()[]{}") -> true
// isValid("([)]")   -> false

This Java code pushes openers and, on each closer, checks that the popped top is the matching opener, returning false on any mismatch or empty stack. After scanning, it returns whether the stack is empty, meaning all openers were closed.

Step-by-Step Walkthrough

A frame-by-frame trace on s = "([)]" (expect false):

graph LR
    F0["'(' push<br/>stack: ("]
    F1["'[' push<br/>stack: ( ["]
    F2["')' closer<br/>top is [ != (<br/>mismatch!"]
    F3["Return false"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This walkthrough tests open-paren, open-bracket, close-paren, close-bracket. We push the paren and the bracket. The close-paren expects a paren on top, but the top is a bracket - a mismatch - so the string is invalid and we return false.

Result: false (the brackets close in the wrong order).

Complexity

Time: O(n) - each character pushed/popped once. Space: O(n) - up to all openers on the stack.

Complexity Comparison

The stack approach is the canonical O(n) solution and the foundation for every bracket-matching variant in this module. Its discipline - push pending openers, reconcile on each closer, require an empty stack at the end - recurs constantly.

Variations & Follow-ups

Why must the stack be empty at the end?

A non-empty stack means some openers were never closed (e.g. "((("). Validity requires every opener to be matched, so leftover openers make the string invalid.

Why check stack.isEmpty() before popping on a closer?

A closer with nothing on the stack (e.g. ")" or "()) ") has no opener to match - immediately invalid. Popping an empty stack would also error.

How does this extend to a single bracket type?

With only (), you don't even need a stack - a counter suffices (increment on (, decrement on ), never go negative, end at zero). The stack is necessary precisely because multiple bracket types must match by kind, not just by count. This counter idea returns in several later problems.

What about edge cases?

• Odd length: Can't be balanced; the algorithm naturally returns false.
• Only closers (")))"): First closer hits an empty stack → false.
• Only openers ("((("): Stack non-empty at the end → false.
• Correctly nested ("([{}])"): Each closer matches the top → true.

Common Interview Pitfalls

• Forgetting the empty-stack check on a closer. Causes an error or wrong result on leading closers.
• Matching by count, not type. "(]" has balanced counts but mismatched types - must compare the actual bracket.
• Not verifying the stack is empty at the end. Misses unclosed openers.
• Using the legacy Stack class. Prefer ArrayDeque for performance.

Why This Problem Matters

Valid Parentheses is the archetype of the standard stack family: push pending state, resolve the most recent item on a matching event, and require a clean stack at the end. This exact skeleton powers expression evaluation, path simplification, and the many bracket variants ahead. If the LIFO discipline clicks here, the rest of the standard family is recombination.

The next topic, Remove All Adjacent Duplicates In String, applies the same push-and-reconcile idea to a different goal: instead of matching opposite brackets, you pop when the incoming character equals the top - collapsing adjacent duplicate pairs in a single pass.

Back to DSA Mastery - Interview Prep, End to End