Yo I couldn’t wait. (Coding Blog) — Week 5.5
I really wanna share this stack problem I talked about a few days ago. Mostly because I had so much trouble with it, but once I got it, I felt euphoric.
So let’s do this! LEEEROYYYYYYY!
This problem is from Elements of Programming Interviews in Python by Adnan Aziz, Tsung-Hsien Lee and Amit Prakash, and the solution is coded in Python 3. If you’re looking for a book to help you with your white board coding in Python/C++/Java, look for Elements of Programming Interviews in your preferred language.
Problem: Balance of Brackets
Write a program that takes as input, a string containing the following characters: {, }, (, ), [, ]. Return whether the string is ‘balanced.’ A string is considered balanced if the number of open and closed brackets of each type are equal, and they’re all paired appropriately.
For example: ‘[][[()(){()}]]’ is considered balanced. ‘][[]]{}{}[‘ is not considered balanced, even though the number of each bracket are equal because they’re not paired appropriately.
Take a minute to solve it for yourself.

This problem might be a little difficult to solve, but let’s break it down to it’s core problem.
We need to determine if a pair is formed properly.
How do we do that? A stack of course!
We’ll make a stack, and push the character to a stack if it’s facing right (i.e. [, (, { ), and pop if it’s facing left (i.e. ], }, )) — BUT only if there’s a right facing bracket of the same type. This is because no matter how interwoven your brackets are, every time a right facing bracket is found, it’s left facing counterpart must be on the top of the stack. We’ll keep track of what a ‘pair’ is by using a dictionary (hash table).
Now that we know the logic behind it, let’s code.
First, we’ll make our function, stack, and a dictionary containing each of our pairs.

Then, we’ll create a for loop that goes through every character, and pushes the character to the stack if it is a key in the dictionary. This deals with all right facing brackets.

Next, we’ll deal with the left facing brackets and if the stack is empty (if a left facing bracket pops up with no right facing brackets in the stack). For this, we’ll simply check for 2 conditions: if the stack is empty, or if the current left facing character matches it’s corresponding right facing character. If it doesn’t, we’ll return false.

The last case we have to deal with is if all the brackets are right facing. I mean, we’ll make it through the string, and we’ll never hit our false return, right? In this case, we’ll just check if the stack has stuff in it. If it does, we return false. If it doesn’t, we’ll return True.

And we’re done! This algorithm has an O(n) run-time in it’s worst case, as we’ll have to go through the whole string. Popping, pushing, and look up in a hash table are all constant operations. It also has an O(n) space complexity, as worst case, we’ll have to append everything to the stack if they’re all right facing brackets.
Next week, we’ll (maybe?) do some binary search tree problems (maybe).
Check out the code on GitHub.
Thanks for the read lad, have a wonderful week. ❤
