In a white boarding session with a coding mentor, we went over an extremely common, easy to medium coding problem that involves using stacks.
The problem is: return ‘YES’ if a series of open and closed brackets, braces, and parenthesis is ‘balanced’. Return ‘NO’ if the string is ‘unbalanced’.
The definition of balanced is: 1) there are as many open braces, parenthesis, and brackets as closed 2) the open and closed are in sequential order and 3) are matching
Examples of ‘balanced’:
“{}[]()”
“{{{[[()]]}}}”
“({{}}[()])”
Examples of ‘unbalanced’:
“(”
“}{”
“[[(}]”
My solution takes two tries. The first just checked to see if the second half of the string matched the first half, which does not account for example one of balanced.
The second solution works (yay!), and uses stacks.
The logic/algorithm is as follows:
- If the character is open, then push onto the stack.
- If encounter a closed, AND the closed matches (see ‘check’ function) the last open one, then we pop the open matching brace/bracket/parenthesis.
This works because the stack changes in ‘live’ time and keeps track to see if the open braces/bracket/parenthesis matches the closed ones.
This is great practice problem and if you are preparing for technical interviews I would highly recommend being familiar with this practice problem.
In the future, I will use stacks to traverse trees. Follow me to keep updated!
