Valid Parentheses in O(n) Time Complexity using JavaScript

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

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

Understanding the Problem

The core challenge of this problem is to ensure that every opening bracket has a corresponding closing bracket and that they are correctly nested. This problem is significant in various applications such as parsing expressions in compilers, validating mathematical expressions, and ensuring the correctness of nested structures in programming languages.

Potential pitfalls include mismatched brackets, incorrect nesting, and unbalanced brackets.

Approach

To solve this problem, we can use a stack data structure. The stack helps us keep track of the opening brackets and ensures that they are closed in the correct order.

Here is a step-by-step approach:

Initialize an empty stack.
Iterate through each character in the string.
If the character is an opening bracket, push it onto the stack.
If the character is a closing bracket, check if the stack is not empty and the top of the stack is the corresponding opening bracket. If so, pop the stack. Otherwise, return false.
After iterating through the string, check if the stack is empty. If it is, return true; otherwise, return false.

Algorithm

Let's break down the algorithm step-by-step:

Create a stack to keep track of opening brackets.
Use a map to store the pairs of matching brackets.
Iterate through the string:
- If the character is an opening bracket, push it onto the stack.
- If the character is a closing bracket, check if the stack is not empty and the top of the stack is the corresponding opening bracket. If so, pop the stack. Otherwise, return false.
After the loop, check if the stack is empty. If it is, return true; otherwise, return false.

Code Implementation


// Function to check if the input string is valid
function isValid(s) {
    // Map to store the pairs of matching brackets
    const bracketMap = {
        '(': ')',
        '{': '}',
        '[': ']'
    };
    
    // Stack to keep track of opening brackets
    const stack = [];
    
    // Iterate through each character in the string
    for (let char of s) {
        // If the character is an opening bracket, push it onto the stack
        if (bracketMap[char]) {
            stack.push(char);
        } else {
            // If the character is a closing bracket, check if the stack is not empty
            // and the top of the stack is the corresponding opening bracket
            const top = stack.pop();
            if (bracketMap[top] !== char) {
                return false;
            }
        }
    }
    
    // After iterating through the string, check if the stack is empty
    return stack.length === 0;
}

// Test cases
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true

Complexity Analysis

The time complexity of this algorithm is O(n) because we iterate through the string once. The space complexity is also O(n) because, in the worst case, we might need to push all opening brackets onto the stack.

Edge Cases

Some potential edge cases include:

Empty string: The function should return true.
String with only opening brackets: The function should return false.
String with only closing brackets: The function should return false.

Examples:

isValid("") // true
isValid("(((((") // false
isValid(")))))") // false

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple balanced strings: "()", "[]", "{}"
Complex balanced strings: "([])", "{[()]}", "({[]})"
Unbalanced strings: "(", ")", "([)]", "((())){"

We can use testing frameworks like Jest or Mocha to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem requirements and constraints.
Break down the problem into smaller, manageable parts.
Consider using data structures like stacks, queues, or hash maps to simplify the solution.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the "Valid Parentheses" problem using a stack-based approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice problems, consider the following resources: