DEV Community

Kimita Kibana Wanjohi
Kimita Kibana Wanjohi

Posted on • Updated on


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

    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]
Enter fullscreen mode Exit fullscreen mode

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
        return False
Enter fullscreen mode Exit fullscreen mode

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 "([{":
            if stack.is_empty():
                is_balanced = False
                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
        return False
Enter fullscreen mode Exit fullscreen mode

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.


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.


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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (1)

erikpischel profile image
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.