Code - backtobackswe.com/platform/content/the-balanced-pa…

Free 5-Day Mini-Course: backtobackswe.com/
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Write a program that tests if a string made up of the characters '(', ')', '{', '}', '[', and ']' is balanced.

Examples

" [ () () () ] { } { [ ( ) ] } " valid
" { } { ) [ ] " invalid

This is another textbook stack problem. Very widely known.

Notice how your brain tries to solve this problem subconsciously. Your eyes will try to scan from left to right keeping track of 2 critical things.

1.) The parentheses that are open
2.) The type of bracket that is open

When the matching closing parenthesis is found you realize that opening bracket is ok, it has been matched, and your mind then worries about the rest of the open brackets.


The Approach

We will scan the string left to right.

The key is that all points we will keep track somehow of the brackets that have been opened (left brackets) but not closed.

When we see a closing bracket we want to be sure that the most recent open bracket is of the same type (and that there even is a left bracket that it is matching).

A stack is perfect for this problem. (the LIFO property is a good fit)


Our Algorithm

-) When we see an open bracket we will push the bracket to the stack, it is now being tracked. It must be closed by the appropriate bracket at some point or else we have a problem.

-) When we see a closing bracket, we peek the top of the stack to make sure it is the correct type of opening bracket.

-) If it is another closing bracket or the wrong type or there is no bracket then we will return false, the parentheses set is not balanced

-) If we get through the whole string without a mismatch then the set is balanced


Time & Space Complexities

Let n be the length of the parentheses of the string.

Time: O( n )

We will traverse the whole string (if it is well formed and execution does not stop later).

The string is length n (has n brackets).

Space:

Worst Case (for valid string)
O( n / 2 ) = O( n )

Worst case, if your string is well-formed, we have to store half of the string if we have all open brackets followed by all matching closing brackets.

Example: " ( ( ( ( ) ) ) )"
n = 8
The stack will hold maximum 4 items at one point in time.



Worse Case (for invalid string)
O( n )

Worst case, if the string is not well-formed, we at worst could get n open brackets that see no matches at all in the string.

n = 8
" ( ( ( ( ( ( ( ( "
The stack will hold maximum 8 items at one point in time.


The Code

All credit for the code in this and many of my other videos go to the authors of "Elements of Programming Interviews" Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech:    / @successintech  

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 9.3 in "Elements of Programming Interviews" by Adnan