Generate Parentheses - Stack - Leetcode 22

0:00 - Read the problem
1:30 - Drawing Explanation
9:55 - Coding Explanation

leetcode 22

#generate #parentheses #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[ryanjensen]

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

[fwan]

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.

[jamesdang]

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.

[arduabeats]

This channel is GOLD. Best coding video solution ever.. clean and simple expaination for preparing coding interview !

[RandomShowerThoughts]

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.

[sleepypanda]

The level of clarity this guy has!!!! You have all my respect neetcoder

[ritwikgopi]

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 👍

[sparrowhk]

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

[DARON]

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!

[sriramkrishnamurthy]

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 🙏🙏😀😀🔥🔥❤️❤️👍👍

[Ashutosh-tj]

Just watched 3 minutes from the starting and I was able to code up the solution. Hats off to you man.

[tarandeepsingh]

You explain things in the best way and make problems look easy

[emekaobasi]

Great explanation, however I still don't understand why you called pop after calling the backtrack function

[midhileshmomidi]

Didn't understand why we do stack.pop(). Any explanation with a small example will be helpful thanks

[abinavravi]

I was struggling a lot with this problem but wonderful explanation of how to break it down to individual components. Thanks a lot

[aryanyadav]

Wonderful explanation! May I ask what would be the time complexity of the backtracking function?

[anniamatthews]

This was definitely a challenging one for me. Thank you for breaking it down the way that you did.

[akshaychavan]

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.

[chrisgu]

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

[GokulRaj-jszn]

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