Generate Parentheses - Stack - Leetcode 22

🚀 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.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@estifanosbireda1892]

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?

[@jayeshnagarkar7131]

can you add more problems to your new site ?

[@mikechu5754]

Thanks! Neetcode. I also recognized the pattern is exactly similar to pre-order depth first search

[@ryanjensen4232]

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

[@findingMyself.25yearsago]

yeah this string solution seems to bit more understandable. Thanks for posting Ryan

[@AnandBaburajan]

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

[@aravind297]

I found the stack confusing, this helped thanks 👍

[@mavaamusicmachine2241]

Isn't appending to a string using that method O(N)? So by using that method we would be increasing our time complexity

[@deepakpandey..]

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..

[@jamesdang5793]

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.

[@triscuit5103]

Same here you mofos

[@chernanq88]

same here

[@gooze3888]

dont use Gods name in vain pls :(

[@StickManVS]

@@gooze3888 oh my god, im so sorry you had to read that

[@fwan0697]

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]

Good point, I think I'll move it

[@vladimirlebedev00010]

@@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

[@samross8060]

@@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 :)

[@sathyapraneethchamala9147]

@@NeetCode +1 still in the stack section

[@moveonvillain1080]

@@NeetCode still in stack 😅

[@arduabeats7003]

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.

[@sleepypanda7172]

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

[@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

[@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 👍

[@DARON121]

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!

[@user-ye4xi4py2k]

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

[@abinavravi1063]

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

[@sriramkrishnamurthy5528]

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

[@tarandeepsingh6345]

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

[@ananya___1625]

Your explanation made me fall in love with this problem!!! Thank you

[@lakshsinghania]

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; } };

[@user-eq4oy6bk5p]

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 ....

[@DanielSilva-sh4bn]

Hey man love your stuff, what program/software do you use for the drawings/illustrations?

[@harryz7973]

really appreciate your explanation - very clear

[@pranavsharma7479]

wow, bro loved the solution and this condition is the main crux of the prob closed_count < open_count to add closed bracket

[@vasumahalingam5162]

The simplicity simply blew my mind. thank you @NeetCode

[@aaronpuah918]

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?

[@arpitsaxena239]

Nope! Everyone needs to learn the technique. After few backtracking problems this one will start looking simple to you.

[@demdimi9316]

If they are not aware of backtracking , no they can't.

[@borisch5894]

@@demdimi9316 chance of stumbling on a problem like this at real life job is very thin tbh

[@rutvaydhami367]

Mind blowing explaination i wish i could understand coding as good as you

[@emmatime2016]

You are amazing!!! You explanation is soooooooo clear! Thank you!

[@vishwaskhurana1217]

Love the explanation, thanks for the video. Can someone please tell the time and space complexity of this ?

[@syafzal273]

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!

[@arunimachakraborty1175]

perfect explanation of a complicated topic. Thank you

[@kartiksoni5877]

Amazing explanation!!!

[@anthonysim563]

Best leetcode channel ever! Thank you for all that you do!

[@akshaychavan5511]

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.

[@binh9495]

Well explained, keep going!

[@chaengsaltz829]

genius analysis and solution... wow!!! I wish I could just bring you to the interview with me! 🤣🤣

[@dera_ng]

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.

[@GokulRaj-js2zn]

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

[@revengehbrevengehb2]

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 (())()???

[@091MW2]

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?

[@halahmilksheikh]

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.

[@nik7867]

There’s no if else there’s only if so backtrack will work fine

[@Flekks]

​@@halahmilksheikhThank you bro. It is so clear explanation.

[@chrisgu7991]

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

[@denysivanov3364]

backtracking with two options has 2^n time complexity, 3 options 3^n etc.. Factorial has factorial time complexity. It all depends

[@li-xuanhong3698]

Love your explanation

[@jjlee7613]

extremely clear explanation thank you

[@NeetCode]

Thanks 😊

[@mavaamusicmachine2241]

super intuitive video thank you for posting

[@pg5353]

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

[@aniruddhvasishta8334]

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.

[@pankajambartani4934]

Awesome explanation !

[@stith_pragya]

Thank You So Much Brother...............This helped a lot........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@bawabigballer]

Amazing Explanation.

[@ucheechesurum7464]

Thanks alot @neetcode for this , looking at your solution i noticed this looks more of a dp solution than stack

[@snehalmdave]

As usual great explanation !!!

[@armaansinghklair3456]

Hey could you make the explanation of time and space complexity of the solution a separate KZbin 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.

[@aerialbaz3802]

If Neetcode hasn't gone into space and time complexities it usually means it is too hard to evaluate that. Hehehe.

[@business_central]

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 ?

[@emekaobasi4765]

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

[@lxu5148]

I am not understanding it well also. Do others have any insights on it?

[@halahmilksheikh]

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.

[@torin755]

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

[@JeffRagusa]

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)

[@alexeymelezhik6473]

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 😂

[@ThinkScienceCanada]

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

[@saurabh95mishra]

thank you, you have been a great help

[@adwaitgharpure3836]

your solutions are actually beautiful

[@VikasGupta-ok9lh]

As always clear and precise explaination

[@ecchioni]

A quick note, if C# or Java are used and you use the built in Stack insert the parenthesis in a reverse order.

[@aryanyadav3926]

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

[@huckleberryginesta7941]

backtracking is basically a loop, its O(n)

[@user-kf5uz6rw4w]

@@huckleberryginesta7941 hm not sure about that. This is basically recursion which is O(2^n)

[@estifanosbireda1892]

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?

[@AbdealiSaria]

anyone know what tools is he using for the starting explaination part, for drawing on screen (which app etc.)?

[@thieninhminh7683]

wow, it's really helpful, thanks very much

[@sellygobeze7173]

phenomenal video 🤯

[@kyanamaaf6314]

Hello, I am confused why we pop the character symbol we just added. Could you explain this?

[@govindsanap5217]

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

[@user-qp2dh6fx9f]

Great Video! thanks for explaining this in a such easy way but can u explain why we need the latter pop ?

[@henrycamelo1]

great explanation!

[@user-sx9xg2rr9r]

short and best explanation for this question❤❤❤❤

[@tabmax22]

These solutions are so much better than Leetcode's 'official' ones

[@varunsharma1889]

great explanation and the diagram

[@100_shubhambrajwasi4]

great solution as usual

[@mekanavyasri9071]

Damn, how can you make anything easy to understand!I really appreciate your work and it is very helpful for me.

[@niko-l-]

Thanks for explanation. BTW, time & space complexity analysis is important

[@sanskarkaazi3830]

What is the time and space complexity for this program?

[@midhileshmomidi3120]

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

[@shashivish2022]

Great explanation..!!!

[@floydian25]

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?

[@user-ry7pn9nq2s]

Same query

[@sanchitmehra1079]

amazing explanation

[@InfoBuzz1130]

excellent explanation amigo

[@swarupsaha9064]

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

[@vijayakumareyunni6010]

Very good explanation

[@Vp5hh]

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.

[@prasunsaxena2830]

What is the Time Complexity?

[@peter9759]

Great explaination

[@funicon3689]

great explanation

[@adilkhatri7475]

legend when it comes to explanation.

[@hemasagar5428]

great explanation i wish i have explanation skills like you

[@ianokay]

That recursion tree is absolutely nuts to have to write out, and nigh impossible to actually visualize without it (8:15)

[@nakulpathak54]

Is this O(2^n) time complexity and O(n) space?

[@EditorsCanPlay]

woah I don't get this, how does this generate every combination when the starting point and conditions are always the same?

[@kaimetaev46]

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 ")".

[@TuanNguyen-bc6dk]

thank you so much!

[@rabbyhossain6150]

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

[@BTC500k]

I like how you spelled "Parentheses" in the coding explanation lol

[@sellygobeze7173]

Thank you!

[@koushika4855]

How do we analyze the time and space complexities for this code? It's a bit confusing to analyze for this approach. Could any of you please guide?

[@vibhavrathee6788]

Simply WOW.

[@josetovar3721]

This is not a stack problem, but a backtracking one.

[@sk_4142]

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?

[@shahed016]

Nicely explained (Y)

[@osinakayahifeanyi1537]

Thank you

[@rajeshg3570]

Nice one.. what's the time complexity of this algorithm ?

[@coleb1567]

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

[@michael_loc009]

Could you give the time complexity for the solution of "Generate Parentheses" problem you demonstrated? @NeetCode

[@stutisinha1394]

Great explanation but I didn't understand what exactly pop() is doing?

[@ayushkathpalia8982]

Hey mate. Great Vidoes. What is the complexity of the above solution ?