HackerRank - Stacks Balanced Brackets

Next one in the CTCI list was a stack question, probably one of the most underrated data structures. The problem can be found here. The main gist is that you get a string and need to determine if the string has properly balanced brackets. So for example…


these would all return:



The problem name gives away the obvious data structure. Just need to push the “left” brackets onto the stack as I get them and then pop them off to comapare against the right ones. If we don’t find a matching one then we know that we aren’t balanced.


Initially I forgot to account for 2 specific cases. The first was a single right bracket, since it’s never added to the stack, the stack was seen as empty. The second one was forgetting to check it the stack had anything on it before popping things off. Both were fairly easy to fix!

def is_matched(expression):
    stack = []
    pairs = {
        "[": "]",
        "{": "}",
        "(": ")"
    for char in expression:
        if char in ["[", "(", "{"]:
        elif len(stack) > 0:
            popped = stack.pop()
            if pairs[popped] != char:
                return False
            return False
    return len(stack) == 0


Runtime: O(n)

Space: O(n)

I need to traverse through the entire string to see if everything matches, so O(n) is the the runtime. Also, the stack will need to store everything and as the size of the string increases so does the stack.


Fun problem involving a stack, would enjoy doing more of these.

Written on November 14, 2016