Are Parentheses Balanced – Interview Question

Are Parentheses Balanced – Interview Question

January 22, 2020 Uncategorized 0

Given a string expression, find out if the parentheses are balanced or not.
Let’s find out how to answer this question in a technical interview.

To begin with, let’s understand the question first. In an expression, you can have different types of brackets or parentheses. You need to check whether they are in correct pair as well as in correct order. You can have 3 different types of brackets: round brackets (), curly brackets {} and square brackets [].
For example, the expression (({})) is balanced. But ({) is not balanced.
Make sure you define the question and its scope with the interviewer before jumping on to the solution.
Upon a brief analysis, you will notice that the last open bracket will be closed first and the first open bracket closes last for a balanced expression. The solution itself points to a data structure that has LIFO property i.e. Last In First Out.
This is a common interview question and it basically tests how familiar you are with Stack data structure.
The basic algorithm will be – you go through the expression one character at a time. For a given open bracket, you push it to the stack. If you encounter a closing bracket, then you pop the stack and check if the popped bracket matches.
If at any point, the parentheses do not match OR at the end of the expression the stack is not empty, we say that the parentheses are not balanced. Otherwise, it’s balanced.

What’s the algorithmic complexity of this solution?
Since you are going through the expression once, the time complexity is simply O(n) where n is the length of the expression.
Since the algorithm is using a Stack and its length on an average will be about n/2, the space complexity is also O(n).

Here is the GitHub Link to the full working solution. I will recommend you to try it on your own before looking at the solution.

Hope you like this interview question. I will be adding more such questions to my YouTube channel. So please do not forget to subscribe.
Until next time, Happy Coding 😊