Valid Parentheses

How it works

Valid parentheses must follow a last-opened, first-closed order — just like stacking plates. So we use a stack to track opening brackets. Whenever we see a closing bracket, we simply check whether it matches the most recent opening bracket on top of the stack. If it matches, we remove that opening bracket. If it doesn't match (or the stack is empty), the string is invalid. A valid string ends with an empty stack.

Steps

1. Create a stack to store opening brackets.
2. For each character c in the string:
   • If it is an opening bracket, push it onto the stack.
   • If it is a closing bracket:
     • Check if the stack is not empty and its top matches the corresponding opening bracket.
     • If yes, pop the stack.
     • Otherwise, return false.
3. After processing all characters:
   • If the stack is empty, return true.
   • Otherwise, return false.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Checking Stack Empty Before Popping

When encountering a closing bracket, you must verify the stack is not empty before checking the top element. Attempting to pop from an empty stack causes an error.

Forgetting to Check if Stack is Empty at the End

After processing all characters, some opening brackets might remain unmatched. The string "(()" processes without errors but leaves "(" on the stack, making it invalid.

Mixing Up Opening and Closing Brackets

When building the bracket mapping, ensure closing brackets map to their corresponding opening brackets, not the other way around. The lookup should happen when you encounter a closing bracket.

Using Wrong Data Structure

Using a queue instead of a stack fails because parentheses follow LIFO (last-in, first-out) order. The most recent opening bracket must be closed first, which requires stack behavior.

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

        for c in s:
            if c in closeToOpen:
                if stack and stack[-1] == closeToOpen[c]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)

        return True if not stack else False

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

        for (char c : s) {
            if (closeToOpen.count(c)) {
                if (!stack.empty() && stack.top() == closeToOpen[c]) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.empty();
    }
};