14

# Checking if a pair of parentheses are balanced in O(n) time and O(1) Space.

I know what you are thinking, "but using a stack we will have `O(n)`

space", yes. But first lets go through stack method for those who are not familiar with with this problem.

I'll be implementing this in python.

In python we can use a list to implement a stack.

```
class Stack():
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return self.items == []
def get_stack(self):
return self.items
def peek(self):
if not self.is_empty:
return self.items[-1]
```

If you are not familiar with stacks. You might find this helpfull

first we start by creating a helper function to check if a pair of parentheses are a match, e.g. `()`

this is a match, `(}`

and this is not.

```
def is_match(p1, p2):
if p1 == "(" and p2 == ")":
return True
elif p1 == "[" and p2 == "]":
return True
elif p1 == "{" and p2 == "}":
return True
else:
return False
```

The main with this function is that it returns True if a pair matches and false if the pair don't match.

Before we code the solution we should first go through how it works and visualize it.

I'll write it in pseudo gibberish first.

```
Function (String containing brackets) # e.g "(({[]}))"
check if the string length is odd or even.
if odd return false. # since the parentheses come in pairs
initialize variables [index = 0, is_balanced = True, n = string_length]
Loop while index < n and is_balanced = True:
get the bracket in string using the index we are at.
if its an opening bracket:
push it to the stack.
else: # its a closing bracket
check if stack is empty:
if empty set is_balaced to false
else: # stack not empty
pop the top element in the stack and compare with the element at our index
if they are not a match:
set is_balanced to false
the increase the index with one.
check if the stack is empty and is_balanced is True:
return True
else:
False
```

Now this is the code

```
def balance_parens(paren_string):
stack = Stack()
index = 0
n = len(paren_string)
is_balanced = True
while index < n and is_balanced:
paren = paren_string[index]
if paren in "([{":
stack.push(paren)
else:
if stack.is_empty():
is_balanced = False
else:
top = stack.pop()
if not is_match(top, paren):
print(top, paren)
is_balanced = False
index += 1
if stack.is_empty and is_balanced:
return True
else:
return False
```

The run time of this is `O(n) time`

and `O(n) space`

, note this is the best I found Online. But I have another way of solving this problem.

my method uses two pointers one at the beginning and the other at the end, then the two pointers work their way to the middle of the string, kinda like attacking it from both ends checking if the brackets are a match.

If it encounters a string like this `()(([]))`

it would return false, coz index 1 and -2 don't match.

*anyone has an idea on how we could solve that? leave a comment*

```
def b_parens(paren_string):
n = len(paren_string)
if n % 2 != 0:
return False
n = n // 2
for i in range(n):
p1 = paren_string[i]
p2 = paren_string[~i]
if not is_match(p1, p2):
return False
return True
```

Since we loop through the array once the time complexity is `O(n)`

and `O(1)`

space.

`~`

tilde is a bitwise operator *NOT*. this might help if you've never heard of it.

Thank you