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.
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.
@@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 :)
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
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
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..
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.
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 👍
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!
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 🙏🙏😀😀🔥🔥❤️❤️👍👍
for those of you that are confused about why the pop, its because he's using the same stack/list for all the recursive calls, this also confused me and i altered the solution a bit in a way that made more sense to me, instead of having to use pop, I just pass a copy of the list/stack for each recursive call and while it uses more memory it still works: def generateParenthesis(self, n: int) -> List[str]: res = [] def paren(leftp, rightp, stack): if leftp == rightp == n: res.append("".join(stack)) return if leftp < n: newlist = stack.copy() newlist.append("(") paren(leftp + 1, rightp, newlist)
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?
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.
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
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 solved this problem but code was too complex and this really helped me out. I chose to add an extra parameter to the backtrack function to keep track of the currentSolution, it uses less memory and is a little bit faster. Thank you so muchhh
Hey could you make the explanation of time and space complexity of the solution a separate UA-cam 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.
Did it slightly differently. Hope this helps def generateParenthesis(self, n: int) -> List[str]: # Create a array to store the result results = [] # Create a function to recursively form parantheses def form_parantheses(combination: str, open_parantheses: int, close_parantheses: int) -> None: # Base case, if the number of close_parantheses > open_parantheses, result is invalid or if the sum of both exceeds total if close_parantheses > open_parantheses or (open_parantheses + close_parantheses) > (n * 2): return # Second Base case, if the number of open_parantheses is equal to each other and to n * 2, we have a valid solution if open_parantheses + close_parantheses == n * 2 and open_parantheses == close_parantheses: results.append(combination) return # We have two decisions here, either we can add an open parantheses or a closed one form_parantheses(combination=combination + "(", open_parantheses=open_parantheses + 1, close_parantheses=close_parantheses) form_parantheses(combination=combination + ")", open_parantheses=open_parantheses, close_parantheses=close_parantheses + 1) form_parantheses(combination="", open_parantheses=0, close_parantheses=0) return results
for those who are wondering about the time and space complexity, lets break it down, for are essentially having 2^n calls in total, because we have 2 choices at each call, and we go n depths, so its 2^n, each time, we are building an array with n of "()", we can say that upper bound, we have about 2^n leaf call (less than this cos there's duplications and etc.). at each leaf call, we are building the ["(()).."] and append it to our res, so this add about n time for each 2^n leaf node. so runtime will be (2^n) * n, (consider n as 2n cos we have '(' and ')'), spacewise, we use backtrack, we only have 1 arr to build it, but the result will be taking 2^n * n space cos we have to store it and return it. so space and time is about the same. i feel that this question should be marked as recursion or backtracking problem rather than stack.
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.
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 (())()???
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 ?
if someone also doesn't understand the use of pop() and global stack, here is my solution with creating a separate stack. maybe it's an extra waste of memory, but I'm not sure def generateParenthesis(self, n: int) -> List[str]: res = []
def dfs(open, close, current): if open == close == n: res.append("".join(current)) return if open < n: dfs(open + 1, close, current + ["("]) if close < open: dfs(open, close + 1, current + [")"]) dfs(0,0, []) return res
Call me pedantic but parenthese is not a word. The singular form is parenthesis. PARENTHESIS! I'd also accept "bracket". Aside from that, amazing video! 👏
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.
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
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?
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!
Nice. Solution without stack: class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def backtrack(open, close, subResult): if open == close == n: res.append(subResult) return if open < n: backtrack(open + 1, close, subResult + '(') if close < open: backtrack(open, close + 1, subResult + ')') backtrack(0, 0, '') return res
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.
As I understood it. We need pop() to pass through all combination since '(((' was built and it is basis for nested combinations. Next is removing one '(' by one and find all possible combination.
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 ")".
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 ....
It took me 2 days to fully understand the question since i was neither Familiar with Trees, DFS nor with Backtracking. so ones who are strictly following the NeetCode Roadmap this question might be a bit tricky to understand. Its Still a Stack question but better suited for Backtracking
Is there any reason why this question couldn't be solved with a breadth first instead of depth first search? I implemented a BFS solution and it seems pretty intuitive. Set a variable like "numParens" to 1 and queue up the string "()". Then, each time you consume the queue, you're adding an additional set of parens everywhere you can in the values you deque. Do this until numParens == n. To do this, consume the queue, and for each value in the queue, insert a set of parens "()" at each index. To avoid duplicates, create a "seen" set before each outer loop (consuming the queue) and only queue up unseen modified values. Once your outer loop breaks (numParens == n) your result is simply everything left in the queue. Is there some reason why this would have worse time or space complexity?
I would't say it's better. It really depends on the language, but in the end it's pretty much the same. This explanation with a stack really helped me grasp the solution better as you are actually poping the element after the recursive call.
You should put this problem under the backtracking category and not under the stack one. This is basically a backtracking problem, the stack here is just a helper DS.
I can't help but think they are possible optimizations here, first the moment you reach open = n you know you can only add closed ones, so if you already have c closed you need to add n-c closed and that's it second most solutions present a symetry, those ones do not need tobr calculated to the end. but it's not all of them so we need a criteria to decide and finally some solutions can be mirrored, but I am unsure we can leverage that as we would need to know which branch hold the mirror and not run it
This link explains why we need to perform pop at the end- stackoverflow.com/questions/67355764/why-do-we-pop-from-the-list-at-the-end-of-each-backtrack-iteration
This is how this can be solved using stack: This is how this can be solved using stack: def insert_char_at_index(s, index, char): return s[:index] + char + s[index:] def generateParenthesis(brackets): brackets_stack = deque() result_stack = deque() for _ in range(brackets - 1): brackets_stack.append("()") if len(result_stack) == 0: result_stack.append("()") while len(brackets_stack) != 0: temp = [] while len(result_stack) != 0: temp.append(result_stack[-1]) result_stack.pop() top = brackets_stack[-1] for k in temp: for i in range(0, len(k)//2+1): res = insert_char_at_index(k, i, top) if res not in result_stack: result_stack.append(res) if len(brackets_stack) != 0: brackets_stack.pop() return result_stack JK, you can use any other data structure
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
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?
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?
🚀 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
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
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 😅
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..
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.
This channel is GOLD. Best coding video solution ever.. clean and simple expaination for preparing coding interview !
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 👍
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!
yeah, 1 ~ 2 years later it is still the same and I really struggled finding what the problem does with stacks.
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.
for those of you that are confused about why the pop, its because he's using the same stack/list for all the recursive calls, this also confused me and i altered the solution a bit in a way that made more sense to me, instead of having to use pop, I just pass a copy of the list/stack for each recursive call and while it uses more memory it still works:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def paren(leftp, rightp, stack):
if leftp == rightp == n:
res.append("".join(stack))
return
if leftp < n:
newlist = stack.copy()
newlist.append("(")
paren(leftp + 1, rightp, newlist)
if rightp < leftp:
newlist1 = stack.copy()
newlist1.append(")")
paren(leftp, rightp + 1, newlist1)
paren(0,0, [])
return res
i was also confused by the pop. thankyou very much
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
Didn't understand why we do stack.pop(). Any explanation with a small example will be helpful thanks
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.
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
I was struggling a lot with this problem but wonderful explanation of how to break it down to individual components. Thanks a lot
This was definitely a challenging one for me. Thank you for breaking it down the way that you did.
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
Wonderful explanation! May I ask what would be the time complexity of the backtracking function?
backtracking is basically a loop, its O(n)
You explain things in the best way and make problems look easy
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 solved this problem but code was too complex and this really helped me out.
I chose to add an extra parameter to the backtrack function to keep track of the currentSolution, it uses less memory and is a little bit faster.
Thank you so muchhh
extremely clear explanation thank you
Thanks 😊
Hey could you make the explanation of time and space complexity of the solution a separate UA-cam 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.
Did it slightly differently. Hope this helps
def generateParenthesis(self, n: int) -> List[str]:
# Create a array to store the result
results = []
# Create a function to recursively form parantheses
def form_parantheses(combination: str, open_parantheses: int, close_parantheses: int) -> None:
# Base case, if the number of close_parantheses > open_parantheses, result is invalid or if the sum of both exceeds total
if close_parantheses > open_parantheses or (open_parantheses + close_parantheses) > (n * 2):
return
# Second Base case, if the number of open_parantheses is equal to each other and to n * 2, we have a valid solution
if open_parantheses + close_parantheses == n * 2 and open_parantheses == close_parantheses:
results.append(combination)
return
# We have two decisions here, either we can add an open parantheses or a closed one
form_parantheses(combination=combination + "(", open_parantheses=open_parantheses + 1, close_parantheses=close_parantheses)
form_parantheses(combination=combination + ")", open_parantheses=open_parantheses, close_parantheses=close_parantheses + 1)
form_parantheses(combination="", open_parantheses=0, close_parantheses=0)
return results
What is the Time Complexity?
for those who are wondering about the time and space complexity, lets break it down, for are essentially having 2^n calls in total, because we have 2 choices at each call, and we go n depths, so its 2^n, each time, we are building an array with n of "()", we can say that upper bound, we have about 2^n leaf call (less than this cos there's duplications and etc.). at each leaf call, we are building the ["(()).."] and append it to our res, so this add about n time for each 2^n leaf node. so runtime will be (2^n) * n, (consider n as 2n cos we have '(' and ')'), spacewise, we use backtrack, we only have 1 arr to build it, but the result will be taking 2^n * n space cos we have to store it and return it. so space and time is about the same. i feel that this question should be marked as recursion or backtracking problem rather than stack.
Love the explanation, thanks for the video. Can someone please tell the time and space complexity of this ?
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.
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 (())()???
wow, bro loved the solution and this condition is the main crux of the prob closed_count < open_count to add closed bracket
A quick note, if C# or Java are used and you use the built in Stack insert the parenthesis in a reverse order.
The simplicity simply blew my mind. thank you @NeetCode
Mind blowing explaination i wish i could understand coding as good as you
Your explanation made me fall in love with this problem!!! Thank you
Personnally, I also didn't understand why this problem was in stack section at first, but considering the low cap on the input value (
Hello, I am confused why we pop the character symbol we just added. Could you explain this?
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 ?
if someone also doesn't understand the use of pop() and global stack, here is my solution with creating a separate stack. maybe it's an extra waste of memory, but I'm not sure
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(open, close, current):
if open == close == n:
res.append("".join(current))
return
if open < n:
dfs(open + 1, close, current + ["("])
if close < open:
dfs(open, close + 1, current + [")"])
dfs(0,0, [])
return res
Call me pedantic but parenthese is not a word. The singular form is parenthesis. PARENTHESIS! I'd also accept "bracket". Aside from that, amazing video! 👏
really appreciate your explanation - very clear
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.
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
Thank You So Much Brother...............This helped a lot........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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)
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!
Nice. Solution without stack:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(open, close, subResult):
if open == close == n:
res.append(subResult)
return
if open < n:
backtrack(open + 1, close, subResult + '(')
if close < open:
backtrack(open, close + 1, subResult + ')')
backtrack(0, 0, '')
return res
short and best explanation for this question❤❤❤❤
genius analysis and solution... wow!!! I wish I could just bring you to the interview with me! 🤣🤣
These solutions are so much better than Leetcode's 'official' ones
perfect explanation of a complicated topic. Thank you
Hey man love your stuff, what program/software do you use for the drawings/illustrations?
time complexity: 2^2n -> you make 2 choices 2n (the tree height) times
space: 2n
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.
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.
As I understood it. We need pop() to pass through all combination since '(((' was built and it is basis for nested combinations. Next is removing one '(' by one and find all possible combination.
This is not a stack problem, but a backtracking one.
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 ")".
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 ....
Damn, how can you make anything easy to understand!I really appreciate your work and it is very helpful for me.
Thanks for explanation. BTW, time & space complexity analysis is important
What is the time and space complexity for this program?
Great Video! thanks for explaining this in a such easy way but
can u explain why we need the latter pop ?
Best leetcode channel ever! Thank you for all that you do!
great explanation
i wish i have explanation skills like you
Whats the time complexity of this solution? On leetcode it says O(n^2) but I'm not too sure why?
Great explanation but I didn't understand what exactly pop() is doing?
It took me 2 days to fully understand the question since i was neither Familiar with Trees, DFS nor with Backtracking. so ones who are strictly following the NeetCode Roadmap this question might be a bit tricky to understand. Its Still a Stack question but better suited for Backtracking
You are amazing!!! You explanation is soooooooo clear! Thank you!
Is there any reason why this question couldn't be solved with a breadth first instead of depth first search?
I implemented a BFS solution and it seems pretty intuitive.
Set a variable like "numParens" to 1 and queue up the string "()". Then, each time you consume the queue, you're adding an additional set of parens everywhere you can in the values you deque. Do this until numParens == n.
To do this, consume the queue, and for each value in the queue, insert a set of parens "()" at each index. To avoid duplicates, create a "seen" set before each outer loop (consuming the queue) and only queue up unseen modified values.
Once your outer loop breaks (numParens == n) your result is simply everything left in the queue.
Is there some reason why this would have worse time or space complexity?
Is this O(2^n) time complexity and O(n) space?
There is a better solution not involving stack, you can just append "(" or ")" as you call backtrack function, depending on condition ofc.
I would't say it's better. It really depends on the language, but in the end it's pretty much the same.
This explanation with a stack really helped me grasp the solution better as you are actually poping the element after the recursive call.
You should put this problem under the backtracking category and not under the stack one. This is basically a backtracking problem, the stack here is just a helper DS.
Nice one.. what's the time complexity of this algorithm ?
Extremely well explained
Amazing explanation!!!
your solutions are actually beautiful
phenomenal video 🤯
concept makes sense but actually implementing it in code is way more difficult. Recursion on this one is hard to understand
I can't help but think they are possible optimizations here,
first the moment you reach open = n you know you can only add closed ones, so if you already have c closed you need to add n-c closed and that's it
second most solutions present a symetry, those ones do not need tobr calculated to the end. but it's not all of them so we need a criteria to decide
and finally some solutions can be mirrored, but I am unsure we can leverage that as we would need to know which branch hold the mirror and not run it
can you explain the pop statement buddy.
I got confused there too. Check this out: ua-cam.com/video/N-3fyoKD8-k/v-deo.html She did not use stack, and there is no pop.
@@ax5344 Sure Buddy
This link explains why we need to perform pop at the end-
stackoverflow.com/questions/67355764/why-do-we-pop-from-the-list-at-the-end-of-each-backtrack-iteration
@@suryadeepchatterjee2172 Thanks buddy
@@shubhammishra6119 aint your buddy guy
This is how this can be solved using stack:
This is how this can be solved using stack:
def insert_char_at_index(s, index, char):
return s[:index] + char + s[index:]
def generateParenthesis(brackets):
brackets_stack = deque()
result_stack = deque()
for _ in range(brackets - 1):
brackets_stack.append("()")
if len(result_stack) == 0:
result_stack.append("()")
while len(brackets_stack) != 0:
temp = []
while len(result_stack) != 0:
temp.append(result_stack[-1])
result_stack.pop()
top = brackets_stack[-1]
for k in temp:
for i in range(0, len(k)//2+1):
res = insert_char_at_index(k, i, top)
if res not in result_stack:
result_stack.append(res)
if len(brackets_stack) != 0:
brackets_stack.pop()
return result_stack
JK, you can use any other data structure
why pop()? seems remove the pop it also works
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
This problem is not related to stacks and is misplaced in the roadmap and caused a lot of confusion.
Thanks alot @neetcode for this , looking at your solution i noticed this looks more of a dp solution than stack
2:02 bro made smiley with out knowing
Love your explanation
anyone know what tools is he using for the starting explaination part, for drawing on screen (which app etc.)?
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?
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?
This question really threw me off in the stack section, since I didnt' really think of recursion at all.
Amazing Explanation.
@neetcode can you please explain the time and space complexity for this problem?
I like how you spelled "Parentheses" in the coding explanation lol
What is the Time and Space complexity?
legend when it comes to explanation.
super intuitive video thank you for posting