# 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:

- Let’s say that while iterating, we get ‘[‘. Since we have an opening bracket, we will add it to a list.
- Then, we get another character ‘(‘. We will also add it to the same list
- 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.
- 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)`

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022