1. Understanding the Problem

You are given a string containing just the characters '(', ')', '{', '}', '[' and ']'. Your task is to determine if the input string is valid.

The Rules of Validity:

• 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.

Quick Examples

• "()" — Valid. Opens and closes perfectly.
• "()[]{}" — Valid. They all close in the right order.
• "(]" — Invalid. Mismatched bracket types.
• "([)]" — Invalid. The order is wrong; you cannot close the parenthesis ) before closing the square bracket ] inside it.

2. The Core Intuition: Think Like a Stack

Imagine you are packing boxes inside of other boxes. Before you can tape up an outer box, you must finish packing and taping up the inner box. This "Last-In, First-Out" (LIFO) behavior is exactly how a Stack works.

Whenever you encounter a new opening bracket, you push it onto the top of your stack. Whenever you encounter a closing bracket, it must match whatever bracket is currently at the very top of your stack. If it doesn't match, or if the stack is empty when you try to close a bracket, the string is invalid.

3. The Logic Step-by-Step

To make the code clean, we can use a Hash Map (Dictionary) to pair our closing brackets with their corresponding opening brackets. Here is the algorithm:

1. Initialize an empty Stack.
2. Create a mapping of closing brackets to opening brackets (e.g., ')' : '(').
3. Loop through each character in the string:
   • If it is an opening bracket: Push it onto the Stack.
   • If it is a closing bracket: Check the Stack. Is it empty? Does the top of the Stack match the required opening bracket? If no, return False. If yes, pop the top bracket off the Stack.
4. At the very end, if the Stack is completely empty, return True (all brackets were matched and closed). If there are still brackets left, return False.

4. Complexity Analysis

• Time Complexity: O(N) — We iterate through the string of length N exactly one time. Pushing and popping from a stack takes O(1) time.
• Space Complexity: O(N) — In the worst-case scenario (e.g., all opening brackets like "((((("), we will push every single character onto the Stack.

5. Code Implementations

Expand the sections below to see the optimal O(N) implementation in your preferred programming language.

def isValid(s: str) -> bool:
    stack = []
    # Map closing brackets to their matching open brackets
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        # If it's a closing bracket
        if char in bracket_map:
            # Pop from stack if it's not empty, otherwise assign a dummy value
            top_element = stack.pop() if stack else '#'
            
            # If the popped element doesn't match the mapped open bracket, it's invalid
            if bracket_map[char] != top_element:
                return False
        else:
            # It's an opening bracket, push to stack
            stack.append(char)
            
    # If the stack is empty, all brackets were matched properly
    return not stack

import java.util.Stack;
import java.util.HashMap;

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        
        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            // If the current character is a closing bracket
            if (map.containsKey(c)) {
                // Get the top element of the stack, or a dummy if empty
                char topElement = stack.empty() ? '#' : stack.pop();
                
                // If it doesn't match the corresponding opening bracket, return false
                if (topElement != map.get(c)) {
                    return false;
                }
            } else {
                // It's an opening bracket, push it onto the stack
                stack.push(c);
            }
        }
        
        // If stack is empty, it's valid
        return stack.isEmpty();
    }
}

#include <string>
#include <stack>
#include <unordered_map>

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> st;
        std::unordered_map<char, char> map = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };
        
        for (char c : s) {
            // If the character is a closing bracket
            if (map.count(c)) {
                char topElement = st.empty() ? '#' : st.top();
                
                if (!st.empty()) {
                    st.pop();
                }
                
                if (topElement != map[c]) {
                    return false;
                }
            } else {
                // It's an opening bracket
                st.push(c);
            }
        }
        
        return st.empty();
    }
};

6. Conclusion: You Are Ready

You have successfully unlocked the Stack data structure. The "Valid Parentheses" problem teaches you how to maintain a history of unmatched elements and resolve them in reverse order. Whenever an interview question involves nesting, matching pairs, or needing to "go back" to the most recent item, your brain should immediately think: "I need a Stack." Keep practicing, and you'll spot these patterns instantly!