Valid Parentheses: Multiple Solutions and Complexity Analysis

The "Valid Parentheses" problem is one of the most classic algorithmic challenges encountered in coding interviews and competitive programming. At its core, the problem asks whether a given string containing only bracket characters—(, ), {, }, [, ]—is valid. A string is considered valid when every opening bracket has a corresponding closing bracket of the same type, and the brackets close in the correct order.

This tutorial walks through the problem definition, multiple solution strategies, their time and space complexity analysis, and best practices you should follow when implementing or extending this algorithm in real-world scenarios.

Problem Statement

Given a string s consisting only of the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid. A string is valid if:

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

For example, "()[]{}" is valid, "([)]" is not, and "{[]}" is valid.

Why It Matters

Beyond being a frequent interview question, the Valid Parentheses problem models a fundamental concept in computer science: the proper nesting of structures. Compilers use similar checks to validate syntax in source code. Text editors and IDEs rely on bracket matching to highlight errors. Configuration parsers, expression evaluators, and even HTML/XML parsers apply the same underlying principle.

Understanding how to solve this problem efficiently teaches you about stack-based algorithms, LIFO (Last In, First Out) data structures, and how to reason about both time and space complexity. These skills transfer directly to more advanced problems such as evaluating arithmetic expressions, parsing nested data formats, and validating tree-like structures.

Solution 1: Stack-Based Approach

The most intuitive and widely accepted solution uses a stack. The idea is simple: iterate through the string, push every opening bracket onto the stack, and when you encounter a closing bracket, check whether the top of the stack contains the matching opening bracket. If it does, pop it; otherwise, the string is invalid. At the end, the stack must be empty.

Implementation

function isValid(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once, and each push and pop operation on the stack is O(1).
Space Complexity: O(n) in the worst case, when all characters are opening brackets and must be stored on the stack before any are popped.

This approach is optimal in terms of asymptotic complexity because you must examine every character at least once, giving a lower bound of O(n) for time. The space usage is also unavoidable in the general case, since you need to remember the nesting structure.

Solution 2: Stack With Early Termination

A refinement of the basic stack approach adds early termination checks to fail fast. If the string length is odd, it can never be valid, so we return false immediately. Additionally, we can combine the opening bracket check and the map lookup into a single pass using a cleaner structure.

Implementation

function isValidOptimized(s) {
    if (s.length % 2 !== 0) return false;

    const stack = [];
    const pairs = new Map([
        ['(', ')'],
        ['{', '}'],
        ['[', ']']
    ]);

    for (let char of s) {
        if (pairs.has(char)) {
            stack.push(char);
        } else {
            const top = stack.pop();
            if (top === undefined || pairs.get(top) !== char) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

Complexity Analysis

Time Complexity: O(n). The early length check provides a constant-time rejection for odd-length inputs but does not change the asymptotic bound.
Space Complexity: O(n) worst case, though the early termination can reduce average-case memory usage for invalid inputs.

Using a Map instead of a plain object can improve readability and provides consistent key handling, especially if you later extend the solution to support additional bracket types.

Solution 3: Counter-Based Approach (Single Bracket Type)

If the problem is simplified to only one type of bracket—say, ( and )—you do not need a stack at all. A simple counter suffices: increment for each opening bracket and decrement for each closing bracket. If the counter ever goes negative, the string is invalid. At the end, the counter must be zero.

Implementation

function isValidSingleType(s) {
    let balance = 0;
    for (let char of s) {
        if (char === '(') {
            balance++;
        } else if (char === ')') {
            balance--;
            if (balance < 0) return false;
        }
    }
    return balance === 0;
}

Complexity Analysis

Time Complexity: O(n).
Space Complexity: O(1), since only a single integer is maintained regardless of input size.

This approach is useful in scenarios like validating balanced parentheses in mathematical expressions where only one bracket type is present. It demonstrates how problem constraints affect the choice of data structure.

Solution 4: Recursive Approach

Although less practical due to recursion depth limits, a recursive solution can validate parentheses by processing the string and tracking an implicit stack through the call chain. This approach is mainly educational, illustrating the relationship between recursion and stacks.

Implementation

function isValidRecursive(s) {
    const pairs = { ')': '(', '}': '{', ']': '[' };
    let index = 0;

    function helper() {
        let stack = [];
        while (index < s.length) {
            let char = s[index];
            if ('({['.includes(char)) {
                stack.push(char);
                index++;
            } else {
                if (stack.length === 0 || stack.pop() !== pairs[char]) {
                    return false;
                }
                index++;
            }
        }
        return stack.length === 0;
    }

    return helper();
}

Complexity Analysis

Time Complexity: O(n).
Space Complexity: O(n) for the stack, plus additional overhead from the call stack in deeper recursive variants.

In production code, prefer the iterative stack approach to avoid stack overflow errors on deeply nested inputs.

Solution 5: Without a Stack (Limited Bracket Types)

For the standard three bracket types, some developers attempt a string-replacement approach: repeatedly remove "()", "{}", and "[]" substrings until the string is empty or no more replacements can be made. While concise, this approach is significantly less efficient.

Implementation

function isValidReplace(s) {
    let prev;
    while (s.length > 0) {
        prev = s;
        s = s.replace('()', '').replace('{}', '').replace('[]', '');
        if (s === prev) break;
    }
    return s.length === 0;
}

Complexity Analysis

Time Complexity: O(n^2) in the worst case, because each replacement pass scans the entire string, and there can be up to O(n) passes.
Space Complexity: O(n) for the intermediate string copies created during replacement.

This solution is not recommended for large inputs but can be acceptable for short strings or quick prototyping. It highlights the trade-off between code simplicity and algorithmic efficiency.

Comparing the Solutions

The table below summarizes the key differences between the approaches discussed:

Stack-based: O(n) time, O(n) space. General-purpose, handles all bracket types, and is the recommended solution.
Optimized stack: O(n) time, O(n) space. Adds early termination and cleaner structure for maintainability.
Counter-based: O(n) time, O(1) space. Only works for a single bracket type but is extremely memory efficient.
Recursive: O(n) time, O(n) space. Educational value but risks stack overflow on deep inputs.
String replacement: O(n^2) time, O(n) space. Simple to write but inefficient for large inputs.

Best Practices

When implementing a Valid Parentheses solution in a real codebase, keep the following best practices in mind:

Choose the right data structure: A stack is the natural fit for nested structures. Resist the temptation to use string manipulation unless the input is guaranteed to be small.
Fail fast: Add early checks such as odd-length rejection to avoid unnecessary computation on obviously invalid inputs.
Use maps for extensibility: Storing bracket pairs in a map or dictionary makes it trivial to add new bracket types later without modifying core logic.
Handle edge cases: Always test empty strings, single characters, strings with only opening brackets, and strings with only closing brackets.
Avoid recursion for unbounded input: Recursive solutions can overflow the call stack on deeply nested inputs. Prefer iteration unless you can guarantee a depth limit.
Write clear, readable code: In interviews and production alike, clarity beats cleverness. Use descriptive variable names and keep the matching logic explicit.

Extending the Problem

The Valid Parentheses problem has many variations that build on the same foundation. Common extensions include:

Multiple bracket types with wildcards: A * character can act as either an opening, closing, or empty bracket. This requires a more sophisticated two-stack or greedy approach.
Longest valid parentheses substring: Instead of a boolean check, find the length of the longest valid substring. This typically requires dynamic programming or a stack with index tracking.
Generate all valid combinations: Given n pairs of parentheses, generate all valid combinations. This is a backtracking problem.
Remove invalid parentheses: Remove the minimum number of brackets to make the string valid, returning all possible results.

Mastering the basic stack solution gives you the foundation to tackle all of these variations with confidence.

Conclusion

The Valid Parentheses problem is a cornerstone of algorithmic problem solving that elegantly demonstrates the power of stack-based reasoning. While the stack approach remains the gold standard for its O(n) time complexity and clarity, exploring alternative solutions—such as counters, recursion, and string replacement—deepens your understanding of trade-offs between time, space, and code simplicity. By following best practices like early termination, map-based extensibility, and careful edge-case handling, you can write robust solutions that scale from interview whiteboards to production parsers. Whether you are validating user input, building a compiler, or preparing for your next technical interview, the principles behind this problem will serve you across a wide range of computational challenges.