LeetCode Solution: 20. Valid Parentheses

Cracking LeetCode 20: Valid Parentheses - A Beginner's Guide to Stacks!

Hey there, future coding rockstars! 👋 NavyaSree_14 here, ready to tackle another exciting LeetCode challenge with you. Today, we're diving into problem 20: "Valid Parentheses". Don't let the name scare you; it's a fantastic introduction to a super useful data structure: the Stack!

The Problem: Are These Parentheses Playing Fair?

Imagine you're writing code, or maybe a complex mathematical expression. You've got different types of brackets: ( ), { }, [ ]. The problem asks us to determine if a given string, made only of these characters, has "valid" parentheses.

What makes them valid? Three simple rules:

1. Matching Pairs: Every open bracket ((, {, [) must be closed by the same type of bracket (), }, ]). You can't close ( with }!
2. Correct Order: Open brackets must be closed in the correct order. Think of it like nesting dolls: the last doll you opened must be the first one you close.
3. No Leftovers: Every close bracket must have a corresponding open bracket. And by the end, no open brackets should be left hanging!

Let's look at some examples to make it crystal clear:

• s = "()"
  • ( opens, ) closes it. Correct type, correct order. Output: true
• s = "()[]{}"
  • ( and ) match. [ and ] match. { and } match. All good! Output: true
• s = "(]"
  • ( opens, but ] tries to close it. Wrong type! Output: false
• s = "([)]"
  • ( opens. [ opens. Then ) closes ( (correct type) but [ was opened after (, so [ should be closed before (. Incorrect order! Output: false
• s = "{[]}"
  • { opens. [ opens. ] closes [ (correct type, correct order for []). } closes { (correct type, correct order for {}). Output: true

The string s will only contain these six characters, and its length can be up to 10,000.

The Intuition: "Who Was Last?" 🤔

How do we keep track of which opening bracket needs to be closed next? When we see an opening bracket, we need to remember it. When we see a closing bracket, we need to check if it matches the most recently opened and yet-to-be-closed bracket.

This "most recently opened, first to close" behavior is the perfect use case for a Stack!

Imagine a stack of plates. When you add a plate, it goes on top. When you remove a plate, you take the one from the top. That's Last-In, First-Out (LIFO).

• When you see an opening bracket, it's like putting a plate on the stack. You remember it.
• When you see a closing bracket, it's like taking the top plate off. You expect it to match the most recently added (top) opening bracket. If it does, great! If not, or if there are no plates (no opening brackets), then something is wrong!

The Approach: A Stack-Powered Validator

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

1. Initialize a Stack: We'll need an empty list (in Python, lists can act as stacks) to store our open brackets.
2. Create a Mapping: To quickly check if a closing bracket has a valid opening counterpart, we'll create a dictionary (or hash map) that maps each closing bracket to its corresponding opening bracket.
   • ')' : '('
   • '}' : '{'
   • ']' : '['
3. Iterate Through the String: We'll go through each character in the input string s one by one.

*   **If the character is an *opening* bracket (`(`, `{`, `[`):**
    *   Push it onto our `stack`. We're remembering that we saw this open bracket.

*   **If the character is a *closing* bracket (`)`, `}`, `]`):**
    *   **Check for an empty stack:** What if we encounter a closing bracket like `)` but our stack is empty? This means there was no corresponding opening bracket. So, it's invalid!
        *   *Pro Tip (from the solution code):* Instead of explicitly checking `if not stack: return False`, we can pop from the stack and assign a special character (like `'#'`) if the stack is empty. This simplifies the next comparison.
    *   **Pop from the stack:** Get the `top` element from our stack. This `top` element represents the most recently encountered opening bracket.
    *   **Compare:** Use our `mapping` to find what the *expected* opening bracket for our current `char` (the closing bracket) should be. Compare this `expected` opening bracket with the `top` element we just popped.
        *   If `mapping[char]` (the expected open bracket) is **NOT equal** to `top` (the actual last open bracket), then it's a mismatch! The parentheses are invalid. Return `False`.

1. Final Check: After iterating through the entire string:
   • If our stack is empty, it means every opening bracket found its matching closing bracket in the correct order. The string is valid! Return True.
   • If our stack is not empty, it means there are some opening brackets left without corresponding closing brackets. The string is invalid! Return False.

The Code: Bringing it to Life

Here's the Python code implementing this stack-based approach:

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

        # Mapping for quick lookup: close bracket -> open bracket
        mapping = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        for char in s:
            if char in mapping:  # If it's a closing bracket
                # Pop the top element if stack is not empty, else assign a dummy value
                top = stack.pop() if stack else '#'

                # Compare the popped element with the expected opening bracket
                if mapping[char] != top:
                    return False
            else:  # If it's an opening bracket
                stack.append(char)

        # After iterating, if the stack is empty, all brackets matched
        return not stack # 'not stack' returns True if stack is empty, False otherwise

Time and Space Complexity Analysis

• Time Complexity: O(N)
  • We iterate through the input string s exactly once. For each character, we perform constant-time operations (dictionary lookup, stack push/pop).
  • N is the length of the input string.
• Space Complexity: O(N)
  • In the worst-case scenario (e.g., a string like (((((((((), our stack could end up storing all N/2 opening brackets.
  • The mapping dictionary uses constant space, as it always stores 3 key-value pairs.

Key Takeaways

• Stacks are for LIFO problems: Whenever you need to process items in a "last-in, first-out" manner (like matching pairs, backtracking, undo operations), think of a stack!
• Mapping for quick lookups: Using a dictionary (mapping in our case) makes it super efficient to check relationships between items.
• Edge cases matter: Always consider what happens with empty inputs, or when the stack is empty at critical points. Our solution handles this gracefully by checking if stack else '#'.
• This problem is a classic and frequently asked. Mastering it truly solidifies your understanding of stacks!

And that's a wrap for "Valid Parentheses"! I hope this breakdown was clear and helpful. Keep practicing, keep coding, and I'll catch you in the next one!

---

Authored by NavyaSree_14 | Published on 2026-05-17 11:25:37