LeetCode 20: Valid Parentheses

Date: January 22, 2026
Category: Arrays
Time Taken: 20 minutes
Difficulty: Easy

---

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Link: Valid Parentheses

---

My Approach

Solution 1 (Brute-Force):

The brute-force solution involves replacing bracket pairs with an empty string. At the end, you simply compare the remaining string to an empty string. If the string is empty, return true; otherwise, return false.

Solution Code

class Solution:
    def isValid(self, s: str) -> bool:
        while "()" in s or "{}" in s or "[]" in s:
            s = s.replace("()", "").replace("{}", "").replace("[]", "")
        return s == ""

Complexity:

Time: O(N²) Space: O(N)

---

Solution 2 (Basic Stack and If-else) [Better]:

• We can define a stack where we will add all the opening brackets.

• Whenever we find a closing bracket, we will check the top element of the stack and compare it with the corresponding opening bracket.

• If it matches, we will pop the opening bracket from the stack. If it doesn't match, we return false.

Solution Code (Basic Stack and If-else)

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

        for char in s:
            if char in "({[":
                stack.append(char)
            elif char == "]" and stack and stack[-1] == '[':
                stack.pop()
            elif char == "}" and stack and stack[-1] == '{':
                stack.pop()
            elif char == ")" and stack and stack[-1] == '(':
                stack.pop()
            else:
                return False

        return not stack

Complexity:

Time: O(N) Space: O(N)

---

Solution 3 (Stack + HashMap) [Best]

• We will create a stack to store the opening brackets.

• We will define a mapping HashMap that links each closing bracket to its corresponding opening bracket.

• Using a for loop, when we find an opening bracket, we will add it to the stack.

• When we find a closing bracket, we will check if the stack is empty. If it is empty, it means the required opening bracket is missing, so the string is not valid.

• If the stack is not empty, we will pop the top element from the stack and compare it with the mapped value for that closing bracket. If it doesn't match, we return False; otherwise, we continue.

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

        for char in s:
            # We found a closing bracket
            if char in mapping:
                # Stack is not empty
                if stack:
                    top_element = stack.pop()
                    # Correct opening bracket
                    if mapping[char] != top_element:
                        return False
                else:
                    return False
            # We found an opening bracket
            else:
                stack.append(char)

        # If stack is not empty -> False otherwise True
        return not stack

Complexity:

Time: O(N) Space: O(N)

---

Key Takeaway: How a stack works in python.

Pattern: Stack Pattern

Series: 90 Days of Data Engineering Progress: 16/90 problems completed

Tags: #DEQuest #LeetCode #Python #DataEngineering #BuildInPublic