Checking if a string of parentheses are balanced in O(n) time and O(1) Space.
Published: 2021-07-26 09:44:00

# First, let's use the stack method.

I know what you are thinking, "but using a stack will result in `O(n)` space." Yes, but first let's go through the stack method for those who are not familiar with this problem. I'll be implementing this in Python.

### Creating a stack

In Python, we can use a list to implement a stack.

```python
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 helpful](https://www.geeksforgeeks.org/stack-data-structure/#:~:text=Stack%20is%20a%20linear%20data,one%20another%20in%20the%20canteen.).

### Solving the balanced parenthesis problem

First, we start by creating a helper function to check if a pair of parentheses is a match, i.e., `()` is a match, `(}` is not.

```python
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 above function takes a pair of parentheses as parameters `p1` and `p2` and checks if the two match.

### The main function

```python
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 runtime of this function is `O(n)` time and `O(n)` space.

### *My solution*

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

#### **Cons**

If it encounters a string like this `()(([]))`, it would return false even though this is balanced because index 1 and -2 don't match. Anyone has an idea on how we could solve that? Leave a comment.

### *Code*

```python
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 the space complexity is `O(1)`. The `~` tilde is a bitwise

 operator _NOT_. [This might help](https://www.arduino.cc/reference/en/language/structure/bitwise-operators/bitwisenot/) if you've never heard of it.

Thank you.