Vansh Aggarwal

Posted on May 16

LeetCode Solution: 20. Valid Parentheses

#leetcode #dsa #programming #tutorial

The Great Parentheses Puzzle: Cracking LeetCode 20 with Stacks!

Hey there, future coding superstar! 👋 NavyaSree_14 here, and today we're diving into a classic LeetCode problem that might seem simple on the surface but teaches us a fundamental data structure concept: Valid Parentheses (Problem 20).

Don't let the "LeetCode" tag intimidate you! We're going to break this down step-by-step, making it as clear as possible. Think of it as a fun puzzle that will level up your problem-solving skills. Ready to unravel some brackets? Let's go!

What's the Puzzle? (Problem Explanation)

Imagine you're writing a math equation or some code. You use parentheses like (), curly braces {} and square brackets [] all the time. But what makes them "correctly" used?

That's exactly what this problem asks us to determine! We're given a string s that contains only these six characters: (, ), {, }, [, ]. Our mission is to figure out if the arrangement of these brackets is valid.

So, what makes a string of brackets valid? Three simple rules:

Matching Pairs: Every open bracket ((, {, [) must be closed by the same type of bracket (so ( needs ), not ] or }).
Correct Order: Open brackets must be closed in the correct sequence. Think of it like peeling an onion: the last bracket opened must be the first one closed. ([{}]) is valid, but ([)] is not.
No Leftovers: Every close bracket must have a corresponding open bracket. You can't just have )) without an opening ((.

Let's look at a few quick examples:

"()" -> True (Simple and perfectly matched)
"()[]{}" -> True (Multiple pairs, all valid)
"(]" -> False (An open parenthesis closed by a square bracket – wrong type!)
"([)]" -> False (Open parenthesis, then open square, but then square is closed before parenthesis. Incorrect order!)
"{[]}" -> True (Looks complex, but [] is inside {}, all matched correctly!)
"[" -> False (An open bracket without a closing one!)

The "Aha!" Moment (Intuition)

When you read a sequence of brackets like "{[()]}", how do you intuitively know it's valid?

You probably keep track of what's "open" and what you're "expecting" to close.

You see {, you think "Okay, I need a } eventually."
Then [, you think "Now I also need a ] before that }."
Then (, you think "And a ) before the ]."
When you see ), you check: "Is the last thing I opened a (? Yes! Great, match found. Forget about (. Now I'm back to needing a ]."
Then ], you check: "Is the last thing I opened a [? Yes! Perfect. Forget about [. Now I'm back to needing a }."
Finally }, you check: "Is the last thing I opened a {? Yes! Awesome. Forget about {. Nothing left."

This pattern of "remembering the last opened item and checking if the current closed item matches it" is a classic use case for a Stack!

A stack is like a pile of plates: you add new plates to the top (push), and when you want to take one, you always take the one from the top (pop). It's LIFO (Last-In, First-Out). This is exactly what we need for brackets: the last bracket we opened is the first one we expect to close.

Our Game Plan (Approach)

We'll use a stack to keep track of all the open brackets we encounter.

Here's the step-by-step breakdown:

Initialize a Stack: Create an empty list (which will act as our stack in Python).
Create a Mapping: We need a quick way to know which opening bracket corresponds to which closing bracket. A dictionary (hash map) is perfect for this! We'll map closing brackets to their opening counterparts: ')' : '(', '}' : '{', ']' : '['.
Iterate Through the String: Go through each character in the input string s one by one.

*   **If it's an Opening Bracket (`(`, `{`, `[`):**
    *   Simply push this bracket onto our stack. We're "remembering" that we've opened it and will expect its corresponding closing bracket later.

*   **If it's a Closing Bracket (`)`, `}`, `]`):**
    *   **Check for an Empty Stack:** First, check if our stack is empty. If it is, it means we've encountered a closing bracket *without any corresponding open bracket*. This is invalid! Return `False`.
    *   **Pop and Compare:** If the stack is *not* empty, pop the top element from the stack. This `top_element` is the *most recently opened* bracket.
    *   Now, compare this `top_element` with the *expected* opening bracket for our *current closing bracket*. We'll use our `mapping` dictionary for this. If `mapping[current_closing_bracket]` (e.g., `'('` for `')'`) is *not* equal to `top_element`, then we have a mismatch (e.g., `(]` or `{[)]`). This is invalid! Return `False`.

Final Check: After checking all characters in the string:
- If our stack is empty, it means every opening bracket we pushed onto the stack eventually found its matching closing bracket. The string is valid! Return True.
- If our stack is not empty, it means there are still some opening brackets left on the stack that never found their closing partners. The string is invalid! Return False.

The Code (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        # Our stack to keep track of opening brackets
        stack = []

        # A dictionary to map closing brackets to their corresponding opening brackets
        # This helps us quickly check if a closing bracket matches the top of the stack.
        mapping = {
            ')': '(',
            '}': '{',
            ']': '['
        }

        # Iterate through each character in the input string
        for char in s:
            # If the character is a CLOSING bracket (i.e., it's a key in our mapping)
            if char in mapping:
                # Pop the top element from the stack if it's not empty.
                # If the stack is empty, it means we encountered a closing bracket
                # without any open bracket preceding it. We use '#' as a dummy value
                # to ensure the comparison fails correctly in that case.
                top_element = stack.pop() if stack else '#'

                # Check if the popped opening bracket matches the expected opening bracket
                # for the current closing bracket.
                # If they don't match (or if stack was empty, top_element is '#'),
                # then the sequence is invalid.
                if mapping[char] != top_element:
                    return False
            # If the character is an OPENING bracket
            else:
                # Push all opening brackets onto the stack to remember them.
                stack.append(char)

        # After iterating through the entire string:
        # If the stack is empty, it means all opening brackets found their matching
        # closing brackets in the correct order. The string is valid.
        # If the stack is not empty, it means there are unclosed opening brackets.
        # So, 'not stack' will return True if empty, False if not empty.
        return not stack

How Fast & How Much Memory? (Complexity Analysis)

Understanding how efficient our solution is is super important!

Time Complexity: O(N)
- N is the length of the input string s.
- We iterate through the string exactly once. For each character, we perform constant-time operations (dictionary lookup, stack push/pop).
- Therefore, the time taken grows linearly with the length of the string.
Space Complexity: O(N)
- In the worst-case scenario (e.g., (((((((((), our stack could end up storing all N opening brackets if they never find their match.
- So, the space required for the stack can grow linearly with the length of the string.

Key Takeaways

Stacks are your friends for order-dependent matching! Whenever you need to match opening/closing items, process things in reverse order of appearance, or manage recursive structures, think of a stack.
Dictionaries for quick lookups: Using mapping for closing -> opening bracket pairs makes our code clean and efficient for comparisons.
Edge cases matter: Remember to handle scenarios like an empty stack when a closing bracket appears, or a non-empty stack at the very end.

This problem is a fantastic introduction to stacks and a common interview question. Mastering it sets a strong foundation for more complex problems!

Happy coding! Keep those brackets balanced! 😉

Authored by NavyaSree_14. Published on 2026-05-16 16:25:05.

DEV Community