To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
I hope y’all had fun with this question yesterday,
This is a classic problem and one that you must know to ace all those interviews. Since you’ve been very supportive, I’ll use let this be open access, so that any of you cautious peeps considering a subscription can catch a glimpse at the quality this newsletter delivers.
This problem can be found as problem 20. Valid Parentheses on Leetcode.
Problem
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
You can test your solution here
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https:/ount.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-
Step 1: Analyzing the trends
As you all know, one of the highest ROI opening moves to help you solve such problems is to simply take small tokens and try to analyze some basic rules and patterns. This can help provide you with a skeleton, around which you can build the solution.
In our case, the first important point to note is the concept of the “correct order”. Based on what we know about Brace notation, this means that the last seen opening brace must be closed first. For example, in ‘{[(‘, the ‘(‘ must be closed first followed by ‘[’ and then the ‘{’. However, our test cases are actually ambiguous and this is a great place to ask clarifying questions. Confirm with the interviewer what ‘correct order’ means
You might feel silly asking such obvious questions, but this actually a great way to stand out. You will highlight your ability to think of alternatives and really consider the consequences, instead of jumping right in. And since most people won’t ask about this, you will be memorable.
Having understood what correct order means, we now start building out the rules.
Step 2: Coming up with the rules
What rules can we come up with to drive our algorithm? Based on our understanding of the problem (and experience with closing braces), we know the following rules apply
Any kind of opening brace can only be closed by the correct closing brace. ) can only close (. The closing-opening pairs are ")":"(", "]":"[", "}":"{".
We can have an arbitrary number of opening braces chained together before closing one. As discussed earlier, we have to close the braces in reverse chronological order.
We can never have a closing brace without its corresponding closing brace first.
Once we have an opening-closing brace pair, we can basically disregard them. ‘([([ ]…’ is functionally equivalent to ‘([(…’.
Looking at all the things we’ve analyzed, an algorithm starts to become clear. Let’s do this next.
Step 3: Building up the Algorithm
Regular readers know that I like to separate the algorithm development stage from the actual coding steps. However, we’ve had a lot of new readers over the last week, so I will just go over the rationale one more time. There are 5 things that make a great developer, that you have to express through your interview. Take a look at them below.
Separating your algorithm part from your actual coding process allows you to highlight both your problem-solving and coding skills equally well. Doing this will also allow you to focus on one thing at a stop, stopping you from getting overwhelmed during the high-pressure interviews. Lastly, breaking down your solution into these steps will allow you to identify which area you need to work on, and which area you want to highlight in your interviews. Remember, as Sun Tzu said in The Art of War, “Know yourself, Know your enemy, and you will win a thousand battles”.
Getting back to the question, let’s start building the algorithm. I’m going to copy the rules we discovered in the last section, so you don’t have to go through them
Any kind of opening brace can only be closed by the correct closing brace. ) can only close (. The closing-opening pairs are ")":"(", "]":"[", "}":"{".
We can have an arbitrary number of opening braces chained together before closing one. As discussed earlier, we have to close the braces in reverse chronological order.
We can never have a closing brace without its corresponding closing brace first.
Once we have an opening-closing brace pair, we can basically disregard them. ‘([([ ]…’ is functionally equivalent to ‘([(…’.
Rule number 2 basically screams LIFO (Last in, First Out). We know that this is where our great buddies’ stacks come into play. Based on rule 2, we know that in our algorithm we want to keep pushing the opening braces we see into the stack.
What happens if we see a closing brace instead? We know it has to close the most recent opening brace- which we find at the top of our stack. We simply pop it, and check if our closing brace is valid for closing it (rule 3). If it is, we continue. If not, we return true.
If we go through the whole string, and our stack is not empty, it means some of the opening braces were never closed. We can return false. If our stack is empty, then we closed everything, and we will return true.
With the details of our algorithm figured out, let’s get into coding
Step 4: Coding it up.
Let’s quickly cover the code for this problem. Once you have the algorithm sketched out, most of it is pretty clear. We use maps/dicts to check if our closing brace is appropriate just because maps have O(1) complexity in lookup and insertion.
class Solution:
def isValid(self, s: str) -> bool:
Map = { ")":"(", "]":"[", "}":"{" }
stack = []
for c in s:
if c not in Map: #c is opening brace
stack.append(c)
continue
if not stack or stack[-1] != Map[c]:
"""
first statement means that we have a closing brace w/o an opening one. Something like ')'
Second or statement just means our closing brace doesn't close the opening one. Like '[)'
In either case we return false
"""
return False
stack.pop()
return not stack
Time Complexity- O(N). We can’t get any better than this because we must go through the string once.
Space Complexity- O(N). We have to store the opening braces in the stack. Worst case is the invalid string with n opening braces, where we end up saving all chars to the stack.
Stay Woke. I’ll see you living the dream.
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75