Vansh Aggarwal

Posted on May 17

LeetCode Solution: 20. Valid Parentheses

#leetcode #dsa #programming #tutorial

Cracking the Code: The Parenthesis Puzzle with Stacks! (LeetCode 20 Explained)

Hey Devs and future competitive programmers! 👋 NavyaSree_14 here, ready to demystify a classic LeetCode problem that's a fantastic introduction to a super useful data structure: the Stack. We're tackling Problem 20: "Valid Parentheses."

Don't let the simplicity of parentheses fool you – this problem teaches a fundamental pattern you'll see in many other coding challenges!

What's the Puzzle? (Problem Explanation)

Imagine you're a compiler, and you need to check if a line of code has all its parentheses, curly braces, and square brackets matched up correctly. That's exactly what this problem asks us to do!

We're given a string s that contains only these six characters: '(', ')', '{', '}', '[', and ']'. Our job is to determine if the string is "valid."

What makes it valid? Three simple rules:

Same Type: An open bracket ((, {, [) must be closed by the same type of bracket (e.g., ( must be closed by ), not } or ]).
Correct Order: Open brackets must be closed in the correct order. Think about nested structures: ([{}]) is valid, but ([)] is not, because the ] is trying to close [ before { is closed.
Every Close Has an Open: Every closing bracket must have a corresponding unclosed open bracket of the same type before it. You can't just have ) without a preceding (.

Let's look at some quick examples:

s = "()" -> True (Simple and perfectly matched!)
s = "()[]{}" -> True (All pairs are distinct and valid)
s = "(]" -> False (Opening parenthesis closed by a square bracket – wrong type!)
s = "([{}])" -> True (Nested, but everything matches up beautifully)
s = "([)]" -> False (Here, the ] closes [ before } is closed. Incorrect order!)

The string length can be up to 10,000 characters. Ready to solve it?

The "Aha!" Moment (Intuition)

When you see an opening bracket, what do you expect? You expect its corresponding closing bracket to appear later. But here's the kicker: if you encounter another opening bracket before the first one is closed, you expect that new opening bracket to be closed first.

This "last one in, first one out" behavior should immediately make you think of a Stack!

Imagine you're reading the string character by character:

When you see an opening bracket ((, {, [), you're essentially "expecting" its closure. You can push it onto a stack. It's waiting for its match.
When you see a closing bracket (), }, ]), this is where the magic happens. You need to check if it matches the most recently opened bracket that hasn't been closed yet. Where is that "most recently opened" bracket? Right at the top of your stack!

If the closing bracket matches the top of the stack, awesome! They cancel each other out, so you pop the opening bracket from the stack. If they don't match, or if there's no opening bracket on the stack at all, then our string is invalid.

Step-by-Step Logic (Approach)

Let's break down the stack-based approach:

Initialize an Empty Stack: This stack will store all the opening brackets we encounter that are still waiting for their match.
Create a Mapping: We need a quick way to know which opening bracket corresponds to which closing bracket. A dictionary (or hash map) is perfect for this! We'll map closing brackets to their respective opening brackets.
- ')' : '('
- '}' : '{'
- ']' : '['
Iterate Through the String: Go through each character char in the input string s.

*   **Case 1: `char` is a Closing Bracket** (e.g., `')'`, `'}'`, `']'`).
    *   First, check if our `stack` is empty. If it is, and we've found a closing bracket, it means there's no opening bracket to match it. This immediately makes the string `invalid`. Return `False`.
    *   If the stack is *not* empty, `pop` the top element from the stack. Let's call it `top_element`.
    *   Now, compare `top_element` with the *expected* opening bracket for the current `char`. We get this `expected` opening bracket from our mapping (e.g., `mapping[char]`).
    *   If `top_element` is *not equal* to `mapping[char]`, it means the brackets don't match (e.g., we popped a `(` but expected a `[`). The string is `invalid`. Return `False`.

*   **Case 2: `char` is an Opening Bracket** (e.g., `'('`, `'{'`, `'['`).
    *   This is simple! Just `append` (or `push`) this opening bracket onto our `stack`. It's now waiting for its corresponding closing bracket.

Final Check: After iterating through the entire string:
- If the stack is empty, it means every opening bracket found its correct match and was popped. The string is valid. Return True.
- If the stack is not empty, it means there are still some opening brackets left on the stack that never found a closing bracket. The string is invalid. Return False.

This approach systematically checks for matching types and correct order using the LIFO (Last-In, First-Out) property of a stack!

The Code

Here's the Python implementation of our approach:

class Solution:
    def isValid(self, s: str) -> bool:
        # Initialize an empty stack to store opening brackets
        stack = []

        # Create a dictionary to map closing brackets to their corresponding opening brackets
        # This helps in quick lookups
        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:
                # Get the top element from the stack.
                # If the stack is empty, assign a dummy value like '#'
                # This prevents errors from popping an empty stack and allows easy comparison
                top_element = stack.pop() if stack else '#'

                # Check if the popped element matches the expected opening bracket
                # If they don't match, or if stack was empty (top_element was '#'), it's invalid
                if mapping[char] != top_element:
                    return False
            # If the character is an opening bracket
            else:
                # Push it onto the stack, waiting for its closure
                stack.append(char)

        # After iterating through the entire string, if the stack is empty,
        # all opening brackets have been correctly closed.
        # Otherwise, there are unclosed opening brackets.
        return not stack # 'not stack' returns True if stack is empty, False otherwise

Time & Space Complexity Analysis

Understanding how efficient our solution is crucial for competitive programming!

Time Complexity: O(N)
- We iterate through the input string s exactly once. N is the length of the string.
- Inside the loop, operations like char in mapping, stack.pop(), stack.append(), and dictionary lookups (mapping[char]) all take constant time, O(1), on average.
- Therefore, the total time complexity is directly proportional to the length of the string, making it O(N).
Space Complexity: O(N)
- In the worst-case scenario, the stack could potentially store all the opening brackets if they are all at the beginning of the string (e.g., s = "(((((((((").
- In such a case, the stack could grow up to a size of N/2 (since at most half the string can be opening brackets if they were to eventually be valid).
- Thus, the space required by the stack is proportional to the input string length, leading to a space complexity of O(N).

Key Takeaways

This problem is a fantastic stepping stone! Here's what we learned:

Stacks are for Matching: Whenever you need to check for matching pairs (parentheses, XML tags, function calls, etc.) that follow a "last-in, first-out" pattern, a stack is your go-to data structure.
LIFO Principle: The core idea behind stacks – Last In, First Out – is perfectly suited for handling nested structures where the most recently opened item must be the first to be closed.
Hash Maps for Quick Lookups: Using a dictionary (or hash map) to store the mapping between opening and closing brackets makes our code clean and efficient (O(1) average time for lookups).
Edge Cases: Always consider empty stacks (e.g., ) at the beginning) and non-empty stacks at the end (unmatched opening brackets).

Keep practicing, and you'll find these patterns appearing everywhere! Happy coding!

Author Account: NavyaSree_14

Time Published: 2026-05-17 11:12:11

DEV Community