Valid Parentheses | LeetCode | Solution Explained

LeetCode 20. Valid Parentheses. I explain a stack based solution in detail. Problem Link.

0. Valid Parentheses: Problem Discussion

0.0. IO Format

• Given:
  • a string of characters: ‘(‘  ‘)’  ‘{‘, ‘}’  ‘[‘ and ‘]’
• Goal:
  • True if the string is valid, False if invalid
  • Valid if:
    • opening brackets are closed by closing brackets
    • opening brackets are closed in the correct order
• Constraints:
  • 1 <= len(string) <= 10 000

0.1. Examples

1. Valid Parentheses: Observations & Logic

1.0. Intuitions

All right. How do we start to think about this problem? If we re-read the problem statement, there’s some thing hidden:

Key point: The restrictions are not on the opening brackets, but the closing brackets.

Reformulating the conditions, we get just one: closing brackets should close only the appropriate opening brackets. Example: “}” should only close “{“

This means that as we iterate, we can:

• add opening brackets: ‘(‘ ‘{‘ ‘[‘ without any conditions
• add closing brackets: ‘)’ ‘}’ ‘]’ with the above single condition

We can maintain a list to do this! I explain how in the next section.

1.1. Resolution

To imagine it better, think of opening brackets getting resolved. Here’s what I mean:

1. Let’s say that while iterating, we get ‘[‘. Since we have an opening bracket, we will add it to a list.
2. Then, we get another character ‘(‘. We will also add it to the same list
3. Then, say we get “)”. What does that mean? This means that we have found a match for the previous “(” we saw! We can simply remove BOTH ‘(‘ and ‘)’ since we have “resolved” it.
4. From this iteration onwards, we can completely forget the existence of BOTH ‘(‘ and ‘)’

2. Valid Parentheses: Implementation

2.0. Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for c in s:
            if c in "{[(":
                stack.append(c)
            else:
                if stack and c == '}' and stack[-1] == '{':
                    stack.pop()
                elif stack and c == ']' and stack[-1] == '[':
                    stack.pop()
                elif stack and c == ')' and stack[-1] == '(':
                    stack.pop()
                else:
                    return False
        
        if stack: return False
        return True

2.1. Complexity Analysis

• Time: O(N), to insert/pop elements. We look at each element only once, as we iterate through the array.
• Space: O(N), worst case when all characters are one of “{[(“. In that case, height of stack will be O(N)

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.