DEV Community

Mridu Bhatnagar
Mridu Bhatnagar

Posted on • Edited on

Day 1 - Balanced Brackets

#python #hackerrank #discuss

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 - https://www.hackerrank.com/challenges/balanced-brackets/problem

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): self.items.append(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=='{'): stack.push(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 break if stack.size() == 0 and result: return "YES" else: return "NO"

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

Top comments (1)

Collapse
 
prathamesh404 profile image
Prathamesh •

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 != '}')):

Thanks.