LeetCode 20 Solution - Valid Parentheses

Problem Statement (LeetCode 20)

Given a string 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 corresponding closing 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

---

Optimal Approach: Stack Data Structure

Intuition

The problem of validating parentheses can be efficiently solved using a stack. The idea is to push each opening parenthesis ('(', '{', '[') onto the stack and, for each closing parenthesis (')', '}', ']'), check if it matches the parenthesis at the top of the stack.

• If it matches, pop the stack.
• If it doesn't match, return false.
• After processing the string, if the stack is empty, then all parentheses are balanced and the string is valid. Otherwise, return false.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        
        // Traverse each character in the string
        for (char c : s) {
            // If it's an opening bracket, push it onto the stack
            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            }
            // If it's a closing bracket, check if it matches the top of the stack
            else {
                if (stk.empty()) return false; // Stack is empty, invalid string
                char top = stk.top();
                stk.pop();
                
                // Check if the top matches the corresponding opening bracket
                if ((c == ')' && top != '(') || 
                    (c == '}' && top != '{') || 
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        
        // If the stack is empty, all brackets were properly closed
        return stk.empty();
    }
};

---

Step-by-Step Explanation of Code

1. Create a Stack:

   • A stack is used to keep track of the opening parentheses. This allows us to check for matching pairs efficiently.

2. Traverse the String:

   • For each character in the string:
     • If it is an opening parenthesis ('(', '{', '['), push it onto the stack.
     • If it is a closing parenthesis (')', '}', ']'):
       • Check if the stack is empty. If it is, return false (as there is no opening parenthesis to match the closing one).
       • If the stack is not empty, pop the top of the stack and check if it matches the current closing parenthesis. If not, return false.

3. Final Check:

   • At the end of the string, if the stack is empty, it means that all opening parentheses have been matched with their corresponding closing parentheses. Return true.
   • If the stack is not empty, it means some opening parentheses did not have matching closing parentheses, so return false.

---

Dry Run with Example

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

1. Initial State:
   stk = [] (empty stack).

2. Step-by-step Processing:

   • Character '(': Push onto the stack. stk = ['('].
   • Character '{': Push onto the stack. stk = ['(', '{'].
   • Character '[': Push onto the stack. stk = ['(', '{', '['].
   • Character ']': Pop '[' from the stack, match with ']. stk = ['(', '{'].
   • Character '}': Pop '{' from the stack, match with '}'. stk = ['('].
   • Character ')': Pop '(' from the stack, match with ')'. stk = [] (empty stack).

3. Final Check:
   The stack is empty, so the string is valid. Output: true.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Check Pair by Pair)	O(n^2)	O(1)	Inefficient because it requires checking pairs repeatedly.
Sorting	O(n log n)	O(1)	Sorting the string does not preserve the order of parentheses.
Stack (Optimal)	O(n)	O(n)	Most efficient approach with a clear mapping of brackets.

---

Why Stack is the Best

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
• Space Complexity: O(n), because in the worst case (all characters are opening parentheses), the stack will store n elements.
• Optimal Solution: This approach ensures that we validate the parentheses in linear time, while the stack provides an easy way to handle the matching of parentheses.

---

Complexity Analysis

• Time Complexity: O(n)
  We traverse the string once, and each operation (push, pop) on the stack is done in constant time.

• Space Complexity: O(n)
  In the worst case, all characters could be opening parentheses, leading to a stack size of n.

---

Conclusion

✅ Best Approach: Stack-based Solution
✅ Time Complexity: O(n)
✅ Space Complexity: O(n)
✅ Optimal for Validating Parentheses in Linear Time

Recommended Problems for Practice

1. Valid Parenthesis String (LeetCode 678)
2. Generate Parentheses (LeetCode 22)
3. Longest Valid Parentheses (LeetCode 32)

🚀 Master Stack Techniques for Parentheses Validation!