DEV Community


Day 1 - Balanced Brackets

Mridu Bhatnagar
Updated on ・1 min read

Below mentioned problem is not a leetcode problem. This was one of the practice problems on Hackerrank.

Complete the function isBalanced in the editor below. It must return a string: YES if the sequence is balanced or NO if it is not.

isBalanced has the following parameter(s):

s: a string of brackets

Problem Statement -

Solution Approach

  1. Iterate over the given string.
  2. If you encounter an opening bracket "([{" push it to the stack.
  3. If you encounter a closing bracket pop the topmost element from the stack.
class Stack:
    def __init__(self):
        self.items = []

    def push(self, element):

    def pop(self):
        return self.items.pop()

    def size(self):
        length = len(self.items)
        return length

    def peek(self):
        return self.items[len(self.items)-1]

def isBalanced(s):
    stack = Stack()
    result = True
    for x in s:
        if (x=='[') or (x=='(') or (x=='{'):
        elif (x == ']') or (x == ')') or (x == '}'):
            if stack.size() > 0:    
                topmost_element = stack.pop()
                if ((topmost_element == '[') and (x != ']')) or ((topmost_element == '(') and (x != ')')) or ((topmost_element == '{') and (x != '}')):
                    result = False
    if stack.size() == 0 and result:
        return "YES"
        return "NO"

Alternate approaches to optimize the solution are welcome. No code snippets. Just discussion. :)

Discussion (1)

prathamesh404 profile image

Disclaimer: If in case violates the requirements, please let me know

  • Was it a necessary constraint to create a stack from scratch? List in python have underlying capability that works like Stack having same time complexity of pop(), append() as O(1),
  • Also a HashMap or dictionary in python to map key: values as{open:close}. Which also has O(1) time complexity for accessing an element. e.g.
mapping = {
  • Code redundancy can be reduced, long conditional statements makes code less readable. e.g. if ((topmost_element == '[') and (x != ']')) or ((topmost_element == '(') and (x != ')')) or ((topmost_element == '{') and (x != '}')):