Valid Parentheses - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Determine if a string of parentheses is valid, where each opening parenthesis has a matching closing parenthesis in the correct order.
Create a hash map mapping closing parentheses (")", "}", "]") to their corresponding opening parentheses ("(", "{", "[").
Initialize an empty stack to store opening parentheses.
Iterate through each character c in the input string s.
If c is not a closing parenthesis (i.e., not in the hash map), push c onto the stack.
If c is a closing parenthesis, check if the stack is empty; if so, return False.
Pop the top character from the stack and check if it matches the corresponding opening parenthesis for c using the hash map.
If they don’t match, return False.
After the loop, return True if the stack is empty (all parentheses matched); otherwise, return False.

Code Solution

class Solution:
    def isValid(self, s: str) -> bool:
        hashmap = {")": "(", "}": "{", "]": "["}
        stk = []

        for c in s:
            if c not in hashmap:
                stk.append(c)
            else:
                if not stk:
                    return False
                else:
                    popped = stk.pop()
                    if popped != hashmap[c]:
                        return False

        return not stk

# Time Complexity: O(n)
# Space Complexity: O(n)

#include <stack>
#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> hashmap = {{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> stk;

        for (char c : s) {
            if (hashmap.find(c) == hashmap.end()) {
                stk.push(c);
            } else {
                if (stk.empty() || stk.top() != hashmap[c]) {
                    return false;
                }
                stk.pop();
            }
        }

        return stk.empty();
    }
};

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        java.util.Map<Character, Character> hashmap = new java.util.HashMap<>();
        hashmap.put(')', '(');
        hashmap.put('}', '{');
        hashmap.put(']', '[');
        
        Stack<Character> stk = new Stack<>();

        for (char c : s.toCharArray()) {
            if (!hashmap.containsKey(c)) {
                stk.push(c);
            } else {
                if (stk.isEmpty() || stk.pop() != hashmap.get(c)) {
                    return false;
                }
            }
        }

        return stk.isEmpty();
    }
}

var isValid = function(s) {
    const hashmap = { ')': '(', '}': '{', ']': '[' };
    const stk = [];

    for (const c of s) {
        if (!(c in hashmap)) {
            stk.push(c);
        } else {
            if (stk.length === 0 || stk.pop() !== hashmap[c]) {
                return false;
            }
        }
    }

    return stk.length === 0;
};

Detailed Explanation

Understanding the Problem: Valid Parentheses

The “Valid Parentheses” problem asks us to determine whether a string of brackets is properly balanced. A string is valid if:

Open brackets are closed by the same type of brackets.
Brackets are closed in the correct order.
Every closing bracket has a corresponding open bracket of the same type.

For example:

"()[]{}" → true
"(]" → false
"([{}])" → true

Why This Problem Matters

This is a fundamental problem in understanding how stacks work. It also has real-world applications in parsing expressions, validating compilers, and building interpreters. It's often one of the first problems used to introduce stack-based algorithms in interviews and technical assessments.

Approach: Stack-Based Matching

A stack is ideal for this problem because of its LIFO (Last In, First Out) behavior, which matches the requirement that the most recently opened parenthesis must be the first to close.

Steps:

Create a dictionary that maps closing brackets to their matching opening brackets: {')': '(', ']': '[', '}': '{'}
Initialize an empty stack.
Loop through each character in the string:
- If the character is an opening bracket ('(', '{', '['), push it onto the stack.
- If it's a closing bracket, check if the stack is empty. If it is, return false — there's nothing to match.
- Otherwise, pop the top of the stack and ensure it matches the corresponding opening bracket from the dictionary.
- If it doesn’t match, return false.
After processing all characters, return true only if the stack is empty (all brackets were matched).

Example Walkthrough

Input: "({[]})"
Execution:

'(' → push → stack: ['(']
'{' → push → stack: ['(', '{']
'[' → push → stack: ['(', '{', '[']
']' → pop '[' → match → stack: ['(', '{']
'}' → pop '{' → match → stack: ['(']
')' → pop '(' → match → stack: []

Stack is empty → return true

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string. Each character is processed once.
Space Complexity: O(n) in the worst case, if all characters are opening brackets and must be stored in the stack.

Edge Cases to Consider

Empty string → valid, return true
Unmatched closing bracket → return false
Nested but misordered brackets → return false
One unmatched opening bracket remaining at the end → return false

Conclusion

The “Valid Parentheses” problem is an elegant introduction to stacks and matching logic. By using a dictionary for bracket relationships and a stack for ordering, we can efficiently determine whether the parentheses are balanced and properly nested. Mastering this technique lays the groundwork for more complex parsing problems in code analysis, math expression evaluation, and beyond.

Get Personalized Support at AlgoMap Bootcamp 💡