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

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.

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.

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.

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

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

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 if you've never heard of it.

Thank you.

Comments

[Erik Pischel]

Just count I guess. +1 for every opening parentheses, -1 for every closeing one. Balance should always be >= 0, otherwise ")(" would be legal, and in the end, balance=0. Different counters for different types of parens.

If "([)]" is illegal then it's more complicated.