# Notes on how to solve the Valid Parentheses problem

## Table of Contents

This series of post is like my coding diary – a place where I jot down what worked (and what didn’t) so that future-me can have an easier go at it. In this post I’ll take a look at the Valid Parentheses problem

## Problem statement

Given a string s containing just the characters `(`

, `)`

, `{`

, `}`

, `[`

and `]`

, determine if the input string is valid.

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.

## Examples

### Example 1:

Input: `s = "()"`

→ Output: `true`

### Example 2:

Input: `s = "()[]{}"`

→ Output: `true`

### Example 3:

Input: `s = "(]"`

→ Output: `false`

## My thought process

The first thing that comes to mind is to have some sort of memory of the open brackets that I’ve seen so far. If I find a closing bracket, I can check if the last open bracket is of the same type. If it is, I can remove it from the memory and continue. If it isn’t, I can return `false`

.

The best structure for this is of course a stack. We are going to add to the stack every time we find an opening bracket and remove from it every time we find a closing bracket. If the stack is empty when we find a closing bracket, we can return `false`

. If the stack has elements when we finish iterating through the string, we can return `false`

. Otherwise life is good and we return `true`

.

I’ll use a new example for this:

```
s = "{[()]}"
i = 0
↓
"{[()]}"
Since { it's an opening bracket
we add it to the stack → stack = ["{"]
i = 1
↓
"{[()]}"
Since [ it's an opening bracket
we add it to the stack → stack = ["{", "["]
i = 2
↓
"{[()]}"
Since ( it's an opening bracket
we add it to the stack → stack = ["{", "[", "("]
i = 3
↓
"{[()]}"
Since ) it's a closing bracket
we check if the last element of the stack is a matching bracket,
it is, so we pop it out → stack = ["{", "["]
i = 4
↓
"{[()]}"
Since ] it's a closing bracket
we check if the last element of the stack is a matching bracket,
it is, so we pop it out → stack = ["{"]
i = 5
↓
"{[()]}"
Since } it's a closing bracket
we check if the last element of the stack is a matching bracket,
it is, so we pop it out → stack = []
We finshed iterating through the string and the stack is empty, so we return true.
```

## My solution

```
class Solution:
# Using a stack
def isValid(self, s: str) -> bool:
stack = []
matching_brackets = {
")": "(",
"]": "[",
"}": "{"
}
for char in s:
if char in matching_brackets.values(): # It's an opening bracket
stack.append(char)
else: # It's a closing bracket
if len(stack) == 0:
# if we don't have any opening brackets in the stack
return False
if stack.pop() != matching_brackets[char]:
# if the last opening bracket is not of the same type
return False
return True
```

## Possible follow-up questions

### Can we do it by using a O(1) memory?

If we don’t use a stack, we can use a counter. We can increment the counter every time we find an opening bracket and decrement it every time we find a closing bracket. If the counter is negative at any point, we can return `false`

. If the counter is not zero when we finish iterating through the string, we can return `false`

. Otherwise life is good and we return `true`

.

Since we have three type of parentheses, we need three counters.

```
class Solution:
def isValid(self, s: str) -> bool:
open_parentheses = 0
open_brackets = 0
open_braces = 0
for char in s:
if char == "(":
open_parentheses += 1
elif char == "[":
open_brackets += 1
elif char == "{":
open_braces += 1
elif char == ")":
open_parentheses -= 1
elif char == "]":
open_brackets -= 1
elif char == "}":
open_braces -= 1
if open_parentheses < 0 or open_brackets < 0 or open_braces < 0:
return False
return open_parentheses == 0 and open_brackets == 0 and open_braces == 0
```

This solution is not as elegant as the previous one, but it’s still `O(n)`

time complexity and `O(1)`

memory complexity.