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

First lets use a stack method.

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.

step 1 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 helpfull

Solving it.

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 solution

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.

Cons

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

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 O(1) space.
~ tilde is a bitwise operator NOT. this might help if you've never heard of it.
Thank you

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

Related Posts