Generate Parentheses - Stack - Leetcode 22
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/generate...
0:00 - Read the problem
1:30 - Drawing Explanation
9:55 - Coding Explanation
leetcode 22
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#generate #parentheses #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Thanks for the content, really appreciated as always but I found this video under the stack section. But isn't it a more of backtracking question?
can you add more problems to your new site ?
Thanks! Neetcode. I also recognized the pattern is exactly similar to pre-order depth first search
Think this problem is significantly easier to conceptualize without a stack. You can just use a path variable in the backtrack function and for the conditions where we call backtrack, use path + "(" or path + ")" along with the updated closedN and openN counts. Using a global stack is a bit confusing IMO.
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(open_n, closed_n, path):
if open_n == closed_n == n:
res.append(path)
return
if open_n < n:
backtrack(open_n + 1, closed_n, path + "(")
if closed_n < open_n:
backtrack(open_n, closed_n + 1, path + ")")
backtrack(0, 0, "")
return res
yeah this string solution seems to bit more understandable. Thanks for posting Ryan
Thank you, I think I agree with you. Here are my iterative and recursive solutions:
Iterative:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
parentheses_stack = deque()
parentheses_stack.append(("(", 1, 0))
while parentheses_stack:
s, open_count, close_count = parentheses_stack.pop()
if open_count < close_count or open_count > n or close_count > n:
continue
if open_count == n and close_count == n:
res.append(s)
parentheses_stack.append((s + "(", open_count + 1, close_count))
parentheses_stack.append((s + ")", open_count, close_count + 1))
return res
Recursive:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(s, open_count, close_count):
if open_count < close_count or open_count > n or close_count > n:
return
if open_count == n and close_count == n:
res.append(s)
backtrack(s + "(", open_count + 1, close_count)
backtrack(s + ")", open_count, close_count + 1)
backtrack("(", 1, 0)
return res
I found the stack confusing, this helped thanks 👍
Isn't appending to a string using that method O(N)? So by using that method we would be increasing our time complexity
Actually, it is confusing how making a change in a function call differs from changing it inside the function. If someone got it please explain to me..
You have this in the stack section of Neetcode but I think it's better in the backtracking section. As someone who is going through neetcode right now, I have reached this problem and it's great to learn but it would be better if it was in the backtracking section since I would be doing repetition on those backtracking questions at that time.
Good point, I think I'll move it
@@NeetCode It is still at stack section and this problem actually blow my mind because of it :D. I wondered how can I use stack in order to solve it but I could not figure out. It would be better to move it imho
@@NeetCode Hey it's still in the stack section, which was a bit of a brain explosion when trying to attempt this question. I look forward to retrying this question once I'm familiar with backtracking, however, as other people have suggested it would be best to move the question to the backtracking section to help out other people in future. Thanks :)
@@NeetCode +1 still in the stack section
@@NeetCode still in stack 😅
I’ve been practicing leetcode for upcoming interviews and I gotta say, your explanations are just so goddamn good. Clear, concise and easy to understand. I don’t know what I would do without these videos.
Same here you mofos
same here
dont use Gods name in vain pls :(
@@gooze3888 oh my god, im so sorry you had to read that
This channel is GOLD. Best coding video solution ever.. clean and simple expaination for preparing coding interview !
As soon as you said opening parentheses are less than the number of closing parentheses I got the answer. Finding the happy/sad paths is a really good way to begin tackling these problems.
The level of clarity this guy has!!!! You have all my respect neetcoder
I was able to come up with the same idea for solving this. But what blown me away was the implementation. I tried to use DFS using graph to solve this literally taking this idea. But the way you did with the backtracking is so efficient in terms of time and memory. Kudos man 👍
I was struggling a lot with this problem but wonderful explanation of how to break it down to individual components. Thanks a lot
I have always admired people who back heir solutions with the recursive tree diagram or the recursive call stack diagram. U have done just that . Thanks and Kudos 🙏🙏😀😀🔥🔥❤️❤️👍👍
Just watched 3 minutes from the starting and I was able to code up the solution. Hats off to you man.
You provide a good explanation to your solution; however, the concept that this problem is meant to focus on is not specifically the stack data structure, it's the backtracking method
hey, while this problem contains a stack and it is under a stack section on your website I think its more about a backtracking approach. So I reckon its better to move it there. Cheers!
You offer one of the best explanations in YT. Keep up the great work! BTW in your opinion do you think most FAANG engineers could solve questions like these if they have never seen or have done something similar before?
Nope! Everyone needs to learn the technique. After few backtracking problems this one will start looking simple to you.
If they are not aware of backtracking , no they can't.
@@demdimi9316 chance of stumbling on a problem like this at real life job is very thin tbh
You explain things in the best way and make problems look easy
Your explanation made me fall in love with this problem!!! Thank you
Hey man love your stuff, what program/software do you use for the drawings/illustrations?
Thanks @NeetCode. Just one quick question. Do you have any suggestions on how to go through the example in virtual interview? I can't imagine trying to explain backtracking solution on code editor ....
wow, bro loved the solution and this condition is the main crux of the prob closed_count < open_count to add closed bracket
Love the explanation, thanks for the video. Can someone please tell the time and space complexity of this ?
really appreciate your explanation - very clear
You are amazing!!! You explanation is soooooooo clear! Thank you!
thank u for the intuition, i helped me to clear the basic concept of recursion
cpp code :
class Solution {
public:
void PrintP(int open, int close, vector &ans, string s, int n){
// as we are doing by recursion
// base condition
if(open == n && close == n){
ans.push_back(s);
return;
}
if(open < n){
PrintP(open+1, close, ans, s + "(",n);
}
if(close < n && close < open){
PrintP(open, close+1, ans, s+")",n);
}
}
vector generateParenthesis(int n) {
// this is a pure recursion qs
// where we have to print all the well-formed parentheses just like printing
// all the subseq
// using backtracking
vector ans;
PrintP(0,0,ans,"",n);
return ans;
}
};
Mind blowing explaination i wish i could understand coding as good as you
The simplicity simply blew my mind. thank you @NeetCode
What makes this algorithm go through all possible combinations? Why doesnt the recursion stop after the first combination [ "( ( ( ) ) )"] is added? Like it seems this algorithm would just go through adding three open parenthesis first and then three closed next and would return from the original backtrack call after its added to the result?
It's difficult to visualize because it's backtracking. Conceptually you can think of it as a DFS exploring each allowed "node" or combination. When the DFS call pops from the call stack, it tries to "explore" other "nodes". So after ( ( ( ) ) ) is added, it backtracks all the way to ( ( where it's allowed to add a ) which eventually gives us ( ( ) ( ) ). Then after it backtracks again to ( ( ) ) and we eventually find another answer.
There’s no if else there’s only if so backtrack will work fine
@@halahmilksheikhThank you bro. It is so clear explanation.
What i observed was if we add two balanced paranthesis the resulting string will also be balanced. So I started with the base '( ) ' for n=1 and just added the same recursively at every index
Yes. The approach I thought of was similar to how to generate the Catalan numbers. You basically just take all the valid strings with n-1 pairs of parentheses and then there are 3 options: You can put () to the left of the string, put () to the right of the string, or put the entire string within a pair of parentheses like ( x ). Any duplicates can be ignored. However, this approach takes a long time because it's recursive. The approach in the video is much faster.
Splendid explanation! The explanation was amazing, however when it came to the code implementation, it just didn't make sense anymore. It took me time [and getting obsessed about backtracking] to realise that backtracking doesn't necessarily have to do with trees. I attempted fleshing out a tree with all the possible decisions so I would just return the leaf nodes - since that's what the explanation basically says. Sooner or later, I had to make more research elsewhere....
I later learnt this [please correct me if I'm wrong]: Backtracking has nothing to do with trees. It's just easier to explain the constraints and the decisions using a tree. I wish someone would've pointed that out earlier 😮💨.... Now I'm going to learn backtracking again WITHOUT THINKING IT'S A TREE PROBLEM. However if there's a way to solve this problem USING AN ACTUAL TREE, please do leave a link in the reply 🙏.... Thanks.
Hey could you make the explanation of time and space complexity of the solution a separate CZcams video chapter?. Great videos btw...I think whenever I'm just reviewing problems via your videos, just having that chapter will make it really easy for people for myself. Thanks.
If Neetcode hasn't gone into space and time complexities it usually means it is too hard to evaluate that. Hehehe.
Best leetcode channel ever! Thank you for all that you do!
Awesome, and I do agree with a comment that this could've gone into the backtracking section. But reguardless super clear explanation and very concise and clear code!
genius analysis and solution... wow!!! I wish I could just bring you to the interview with me! 🤣🤣
Well explained, keep going!
Amazing explanation!!!
Great Video! thanks for explaining this in a such easy way but
can u explain why we need the latter pop ?
What would the time complexity of this backtracking algo be? How would u analyze the time complexity of recursive algos I find it pretty hard sometimes to do that
backtracking with two options has 2^n time complexity, 3 options 3^n etc.. Factorial has factorial time complexity. It all depends
Can someone tell me the space complexity? I thought to consider the combination formula but we do have rules for neglecting invalid parenthesis, and it's confusing. and the time complexity is O(4^n), right?
extremely clear explanation thank you
Thanks 😊
Wonderful explanation! May I ask what would be the time complexity of the backtracking function?
backtracking is basically a loop, its O(n)
@@huckleberryginesta7941 hm not sure about that. This is basically recursion which is O(2^n)
Great explanation, however I still don't understand why you called pop after calling the backtrack function
I am not understanding it well also. Do others have any insights on it?
The reason why is because stack is a global. You have to keep the stack in sync with how the backtracking recursions are behaving. So if you tell the code that we're going to add a (, after when you're done with that backtrack, you have to remove it so the stack is consistent for the next possible recursions.
To put it simply: Each time you push the ( or ) onto the stack, you are effectively saying "Now we're branching off to all possibilities after adding a (" or the same for ")". In the tree he showed, the push onto the stack is just done for each point a node branches out to more nodes, hence we pop it off when we want to go back up the tree and down a different branch
stack keeps track of a single branch of the tree (a single value in the result array), but its being repeatedly passed down each path... need to clear it on the way back up for reuse down the next tree branch. (could also have cloned the stack before pushing onto it... or use an immutable string instead of a stack)
The confusion here might lie because of a false impression that recursive calls of many branches are executed in parallel, indeed they are not, so think about that like this - every path of a tree gets traversed till a final node ( well, leaf ) _consecutively_, though recursive nature of the code does not give such an impression.
That means on every hop of this traversal we just add another element to stack , now when we go back ( traverse reversely ) on every hop we do exactly opposite - remove one element from stack , so we end up with empty stack on the top when we return from the rabbit hole of recursive calls. I still think it’d be better to avoid that complexity and just pass stack or array as a recursive procedure call parameter , this would avoid this type of question 😂
I don't understand how the code produces all 5 different outputs for when the case is 3 (as example). I only understand how it does the following one: ((())), but how does it randomly generate the other solutions such as (())()???
perfect explanation of a complicated topic. Thank you
I felt below solution to be more intuitive to understand:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def back_track(string, leftCount, rightCount):
if len(string) == n * 2 :
res.append(string)
return
if leftCount < n:
back_track(string + '(', leftCount + 1, rightCount)
if rightCount < leftCount:
back_track(string + ')', leftCount, rightCount + 1)
back_track('', 0, 0)
return res
Hey, did you explain about the time complexity in this video? I've watched and I didnt see... I asked chatGPT about it and explained about O((4^n)/(n^(3/2)) time
anyone know what tools is he using for the starting explaination part, for drawing on screen (which app etc.)?
super intuitive video thank you for posting
Thanks alot @neetcode for this , looking at your solution i noticed this looks more of a dp solution than stack
I have tried to do this in following way. which i think is a lot simple.
op, cl= n, n #open_counter, close_counter
arr=[]
def par(s, op, cl):
if op==0 and cl==0:
return arr.append(s)
if op>0: #if open parentheis available
par(s+"(", op-1, cl)
if cl>0 and cl>op: #if close parentheis available and close cannot be there before open
par(s+")", op, cl-1)
par("",n, n)
return arr
Can someone explain to me why we do not use a set for the res variable? I know it works, but how come it doesn't fall into making duplicates ? Can anyone clarify that please ?
A quick note, if C# or Java are used and you use the built in Stack insert the parenthesis in a reverse order.
Hello, I am confused why we pop the character symbol we just added. Could you explain this?
Great explanation, but how would you explain the time and space complexities? I believe it's bounded by the nth Catalan Number. How in the world am I supposed to prove that during an interview?
Could you give the time complexity for the solution of "Generate Parentheses" problem you demonstrated? @NeetCode
Thanks for explanation. BTW, time & space complexity analysis is important
What is the time and space complexity for this program?
Thank You So Much Brother...............This helped a lot........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Love your explanation
Awesome explanation !
As usual great explanation !!!
wow, it's really helpful, thanks very much
What is the Time Complexity?
How is the solution ensuring the property of balanced parenthesis ?
Nice one.. what's the time complexity of this algorithm ?
Amazing Explanation.
I came up with this solution without watching this video -
def generateParenthesis(self, n: int) -> List[str]:
result = []
def recursiveParenthesis(n, op = 0, cl=0, current=""): # 'op' means opening bracket count and 'cl' means closing bracket count
if op>n or cl>n or cl>op: return
if len(current) == 2*n: result.append(current)
recursiveParenthesis(n, op+1, cl, current+"(")
recursiveParenthesis(n, op, cl+1, current+")")
recursiveParenthesis(n)
return result
Glad that the approach is almost similar.
Can someone please explain the stack.pop() part. I can't understand why are we removing the value from stack. Wouldn't we need to append it to res at the end?
Same query
That recursion tree is absolutely nuts to have to write out, and nigh impossible to actually visualize without it (8:15)
These solutions are so much better than Leetcode's 'official' ones
Is this O(2^n) time complexity and O(n) space?
Didn't understand why we do stack.pop(). Any explanation with a small example will be helpful thanks
@neetcode can you please explain the time and space complexity for this problem?
thank you, you have been a great help
As always clear and precise explaination
Damn, how can you make anything easy to understand!I really appreciate your work and it is very helpful for me.
What is the Time and Space complexity?
Hey mate. Great Vidoes. What is the complexity of the above solution ?
I found this problem on the stack sections on the leet code roadmap, To me this seem more like a backtracking problem. Am i getting this wrong. is this intentional.
woah I don't get this, how does this generate every combination when the starting point and conditions are always the same?
Ez. Your conditions doesn't stop the execution. So on the second stage of recurtion (when you already have one open "(" ) you will call both backtrack functions for another one open "(" and one for the closed ")".
your solutions are actually beautiful
Such a brilliant solution! I m struggling with backtracking and recursion in general because I can't seem to visualize, any tips?
Keep track of the function call that you are in and make sure to not confuse it with the function call being made.
Would the solution work if u did if/else if/else instead of 3 ifs?
Great explanation but I didn't understand what exactly pop() is doing?
It’s weird. I get the idea here, or at least I think I do. But something about implementing it in code is really hard for me at this stage. But I’m better than where I was not long ago, so I’ll keep working at it
can anyone explain why we pop after the call? Thanks so much
why pop()? seems remove the pop it also works
what is the time complexity?
phenomenal video 🤯
i did not understand the stack.pop() for cleanup part. Can some please explain?
great explanation
i wish i have explanation skills like you
My question is how does it keep track of the combinations of brackets made
great explanation and the diagram
I like how you spelled "Parentheses" in the coding explanation lol
can someone please explain why pop is used?
In the recursive solution you build the state before recurring then once you return you restore the state it was prior to the recur.
i did not understand the flow , after the return statement in backtrack function
can anyone explain it to me plese
Let's take n = 2.
We make the function call Backtrack (0,0) where n =2
There are there conditions: openN=closeN=n, openN
great solution as usual
I understand the decision tree. How does it translate into the code you wrote?
each if statement creates a unique branch
Why do we have to do the stack.pop() after every backtracking? I didn't get the logic there!
What would the time complexity of this algorithm be?
anyone has suggestions in how to master backtrack? I understand backtrack everytime I saw the solutions, but I still dont know how to implement it by myself
Great explanation..!!!
great explanation!