N-Queens - Backtracking - Leetcode 51 - Python

[@NeetCode]

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

[@wookyumkim4669]

I love so much the idea of using posDiag set and negDiag set. That is the truly brilliant trick.

[@nameless2850]

Right? It truly is fascinating

[@nachiket9857]

It's so good, who even comes up with these!

[@illu1na]

@@nachiket9857 y = mx + c and for posDiag y = -x + c so c = y +x, and negDiag y = x +c so c = y-x. Note that the gradient is -1 for posDiag and 1 for negDiag since the given array starts 0 top row and increases as it goes down.

[@davidbujosa]

truly

[@demaxl732]

I was fascinated. How can one even think of this!

[@Cld136]

Backtracking never been this easy after watching your video! Thanks for the excellent intuition about backtracking.

[@harishsn4866]

such an elegant and simple solution without having to pass through loads of different function unlike other videos I've seen. Thank you for this.

[@salehsaeed5734]

I have been watching several videos on n-queen, your video is the most understandable

[@NeetCode]

Thanks, happy it was helpful! 😃

[@CostaKazistov]

When I am stuck on a problem, I like to watch 2-3 videos from different channels. Then it "clicks". Most success I had when it "clicks" on the first go, is when I watch NeetCode.

[@arjunv1624]

Like the clear explanation of the problem and the code walkthrough. Please provide your analysis on the time/space complexity for each problem you are solving.

[@rajrsa]

I had seen this problem for the first time about 7 years ago in uni and I was too scared to even attempt it. Thanks for explaining it so beautifully and helping me conquer my fear. (I was so stupid to be scared of this problem lol)

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@chaitu2037]

I was a bit confused by the problem statement, but your explanation made it looks as simple as possible. Thanks for making such amazing content.

[@vesicapiscis9717]

This is the best video on backtracking I've seen so far. It was so good that I applauded after watching it.

[@jadkhalil9263]

Easily the best explanation on the internet thank you so much for your contributions :)

[@umutkavakli]

I can't express how this explanation blew my mind! You're the best, thank you.

[@frankl9634]

Thanks!

[@NeetCode]

Hey Frank - thank you so much, I really appreciate it!! 😊

[@slygg]

Altough it's an understandable reflex to use a 2d-array to represent this chess board, since a normal chess board is a matrix, in this case that's subobtimal. Since the problem definition is so that you can have only one queen/row anyways you can just get away with a regular array. When you do this checking for conflicts also becomes less computationally expensive since you can just do this: Let b equal chessBoard, if b[row] == b[i] || abs(b[i] - b[j]) == abs(i - j)), conflict found. This probably doesn't matter for small n but once n gets moderately large every little bit starts to add up, especially if your method is time complexity O(n!) as in the video here.

[@symbol767]

Awesome, I solved it by using a helper to iterate through the rows then columns, then diags each separately O(N) for each of those loops, but this way is much better. Thanks man

[@karankanojiya7672]

OMG that diagonal intuition 🤐 Respect ++ Sir!

[@NeetCode]

Thanks! :)

[@SameenIslam]

You explain difficult to understand concepts with amazing clarity, thank you for your work!

[@onlinealias622]

I started doing this problem and it was tricky, but the first part of the vid set me on the right track to code it up myself. Thanks bro

[@parthsalat]

Thanks for speaking clearly...was able to watch this on 2x

[@LeeK301]

Brilliant solution; I learned a lot from the whole concept of (r+c) and (r-c); really great learning content.

[@kwetuligee8087]

My best explanation of n-queens problem. Thank you!

[@Adarsh-mn7pl]

This is the most cleanest approach to this problem, specially using sets to check Validity

[@wessamyaacob1505]

AWESOME! The best channel every for explaining problem-solving questions and how to think about them, rather than just throwing the solutions in front of the audiences. ❤

[@NamasteSaurav]

Shortest and best solution I have even seen. Thank you @Neetcode

[@WBPCS]

I learnt something from this video. You explained it very clearly and concisely. Thank you!

[@alibagheri]

Can't believe I solved this on my own (after 1.5 hours of thinking)!

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@DanielTruongDev]

For those who confused what's the purpose of backtrack(0) code, it's basically call the backtrack function starting at row 0

[@airatvaliullin8420]

Awesome! Mistakenly I used to iterate through all squares in a nested for-loop (similar to how we solve sudoku using backtracking). Now I see that there's no need in that.

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@manojjain3501]

Just one word "Genius". What you know belongs to you what you can let other know that is the Talent. Kudos.

[@vinaf4494]

Very helpful! Very clear with explanation in coding as well. You are the best mentor in my learning way!

[@carloslazarin]

very clever approach using negative and positive diagonals.. thx a lot for sharing!

[@lesterdelacruz5088]

the posDiag and the negDiag set is pretty clever. Makes the code so much more concise.

[@Karim-nq1be]

I find this solution beautiful, and your explanation is very clear as usual, but at the same time it's not that obvious to see what's going on for the execution stack. Thank you again.

[@bommes9802]

They made us solve this in my freshman year of college 💀 some of these guys never coded a single line in their life before that year lol

[@The6thProgrammer]

Awesome solution, you simplified what I was trying to do greatly

[@VysePresidentGeo]

While I was able to solve this myself quite easily, the use of sets - particularly the posDiag and negDiag sets - are incredibly elegant and I appreciate the tip. Thank you so much for your help!

[@tanayasharma7776]

this is the best explanation i've found so far

[@hyk-f4r]

@Neetcode you are amazing as always just want to let you know I appreciate your channel and big thank you for these videos. If at all I clear the interview I sure will send at-least bag of chocolates to you.

[@eshwarprasad2541]

This explanation is simple and to the point. Loved it. Can you make a video on how to frame backtracking logic for any unseen backtracking question. How to frame the logic.

[@robyc9545]

This dude is a legend. Was wondering how you come up with this solution? Did you learn this at school? Do you consult with any resources?

[@Cakie-so5gv]

In terms of the time complexity, don't forget cloning the memory of the board (n^2), except for it, I think the time complexity would be O(n*n!), cuz your tree has n layers, n! is just the number of the bottom level, so the total time complexity I think is O(n!*n + n!*n^2) = O(n!*n^2), that's why the bounce of n is pretty tiny (1

[@amrutaparab4939]

You are a blessing to this world!

[@ivantishchenko4686]

Superb explanation as usual. Calm and thought out.

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@yassineacherkouk]

Always after i came up with the brute force algorithm with some optimization i always come back to the channel to see how the work is done.

[@ilanaizelman3993]

Best explanation I have seen. Thanks!!!

[@nuamaaniqbal6373]

I wish i could break down things as elegantly as u do in ur videos!!

[@ameynaik2743]

What is the time complexity of this solution?

[@Cakie-so5gv]

In terms of the time complexity, don't forget cloning the memory of the board (n^2), except for it, I think the time complexity would be O(n x n!), cuz your tree has n layers, n! is just the number of the bottom level, so the total time complexity I think is O(n!*n + n!*n^2) = O(n!*n^2), that's why the bounce of n is pretty tiny (1

[@EranM]

wow. simply fkn wow with the pos diag neg diag.. such a nice pattern to this.. holy moly. neet! 1337!!

[@chliang3499]

pretty genius way to detect collision of diagonal!!

[@santhosh20071993]

You Just Nailed the Power of Python.

[@leonscander1431]

Damn, the difficulty is in this diagonal trick, the backtracking itself is pretty straightforward.

[@puckwang6850]

The posDiag and negDiag solution is amazing!

[@piglovesasy]

I like this approach!

[@palakjain2505]

you are amazing! thank god this video exists! I am confused what the time complexity of this approach would be??

[@vatsalsharma5791]

Much needed ❤️

[@sagarchawla4926]

Your explanations are amazing.

[@DeGoya]

The Big O time complexity of his solution is 2^(n*n) I guess because let's take 4 as n. We have 2^n options for the first row which is 2^4 = 16. Then for every option we multiple times 2^4 for the second row and so on. That means we would have 2^n^n which is 2^(n*n).

[@summaiyaparveen8730]

Thank You So Much for this amazing Explanation!!

[@thisisankitgaur]

What do you eat man? Seriously, you make Backtracking problems look like a joke. Thanks for the solution!!

[@kunafeh]

Thanks for this amazing explanation. Loved it! 😍

[@saswatmishra4055]

i have a doubt..why do we have to do a clean up after calling the first backtrack function(why do we need to remove all the cols and set the board[r][c] again to "."?

[@bas5rocker311]

this is because we need to check if any other ways of placing the Queen exists. So the sets would be used to keep track of only one Queen before the current row

[@zahraBatenin]

The explanation was great! thanks

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@rishabhnitc]

great, this helped me optimize my otherwise lengthy solution.😍

[@Method5440]

I see why we have to keep track of the column, posDiag and negDiag for each placement of the queen. Is the fact that queen placement also excludes the row hidden by the fact that we’re recursing over the rows atomically?

[@sudeepdalai]

This solution is elegant and ingenious. 🤩🤩

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@pythonfamily]

wow, you nailed it. Thanks a lot

[@knightye]

the c on line 16 is actually presenting all the rows. Using 'c' is better for visualization

[@sushilkhadka8207]

Great explaination ...Love from Nepal Hope you upload more videos

[@winstonkoh672]

Hi NeetCode, thank you for the amazing explanation

[@yinglll7411]

For people wondering what's the time complexity for this solution, I guess its O(n*2) because we are essentially taking a brute force approach, trying out all combinations of rows and columns implies (n*n). Please correct me if i'm wrong😇

[@veliea5160]

to me seems like O(N!). because first we have n options, in the second row we have (n-1) options and then (n-2) and so on

[@Cakie-so5gv]

@@veliea5160don't forget cloning the memory of the board (n^2), except for it, I think the time complexity would be O(n x n!), cuz your tree has n layers, (n!) is just the number of the bottom level. so the total time complexity I think is O(n!*n + n!*n^2) = O(n!*n^2), that's why the bounce of n is pretty tiny (1

[@fredtrentini6791]

It's insane to me how leetcode hard problems have such peculiar domain-specific techniques. I just solved that problem but I had no idea about the posDiag / negDiag pattern and I don't think I would figure it out on my own either, what I did instead was using a cached function that returns a single set with all the "forbidden" (i, j) positions, which led me to a ~3000ms solution rather than a ~60ms solution (good enough I guess but definitely not ideal).

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@krisrocker437]

Great explanation!!! Keep it up, neetcode!

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution.

[@tarangnima4641]

Amazing Explanation..💥

[@spy9740]

Thanks for the content bro

[@zappist751]

Best explanation yet!

[@sahilchoudhary1473]

You are the best neet code

[@nderimbunjaku]

Great explanation, thank you very much!

[@supervince110]

Such an elegant solution!

[@Iamnoone56]

what is time complexity? and what is the diff between board = [["."]*n for i in range(n)] board = [["."]*n]*n anyone? Thanks

[@denshaSai]

the second *n, I believe does not make a deep copy, but points to a single of row ['.']

[@hamoodhabibi7026]

it's the same

[@shivigupta6524]

I have a doubt, by your solution, it will consider duplicate chessboard added to your result do you consider only unique solution in your appoarch?

[@Eria196]

I don't understand... When will the remove functions ever be reached... It's like backtrack(r+1) is stopping them from being reached... Can someone explain to me this... I beg... Am not understanding this solution. Coz r is increasing by one on restrictions. I feel like its going to be equal to n one time n then we shall just return the copy appended in the result

[@MohitJayee]

Why can't we do column - row for positive diagonal? It also gives 0 as constant value.

[@orangethemeow]

You made this problem so easy :)

[@NeetCode]

Glad it helped!

[@chrisaa100]

One Question, Why can't we use regular variable instead of set to track posDiag and NegDiag, Since the values will be same.

[@tnmyk_]

Excellent explanation!

[@imtsrk04]

GOAT for a Reason!!!

[@UnfinishedYara]

thank you so much youre a hero!

[@nhrtsa9010]

No!!! he's a super hero !

[@SurbhiSingh-t2o]

could you please also explain intuition behind TC ?

[@mapo5959]

genius solution. how do people have the insight to come up with this in anything less than a whole day

[@ayushkathpalia8982]

What is the time and space complexity of the above solution ?

[@manubachhal404]

Now ,i understood why channel name is Neetcode.

[@ValhaVaiyagam]

Hi Navdeep, Need a help ..how do u draw ? what tool u use ?

[@rohanchess8332]

I tried writing board = [['.']*n]*n, and rest all the exact same code, but it was giving the wrong output, why?

[@disha4545]

What would be the time complexity ? O(n*n) ?

[@AbyssiniaBenchmark]

Man you are awsome. Really awesome.

[@karandhinakaran1420]

Great Explanation! Keep up the good work! Just an observation that if we use list instead of set, the code is faster by 6ms and saves about 0.1MB of space.

[@mostinho7]

Thanks TODO:- Take notes Backtracking the positions of the queens, but since queens can move horizontally vertically and diagonally, we can’t put two queens together in the same row (because they move horizontally so would attack each other) and also can’t put them in same column or diagonal. So when backtracking, we place queen in a position in row and make recursive call to place the other in next row and keep track of: Column that queen was placed in Both diagonals of the queen (YES there are TWO diagonals that the queen can move in, positive slope and negative slope, so need to keep track of both)

[@shoooozzzz]

if you ask this question in an interview, you are what is wrong with the hiring process

[@NeetCode]

true dat

[@realworldcodingapplications]

This is 2nd backtracking problem I’ve seen, the line I don’t get is the remove line, so you’re adding everything to set just to remove it afterwards?

[@Eddie-um6cw]

I don't understand this part: res.append (copy) return Can anyone help me what does that return mean? Does it return nothing or smt?

[@prafulparashar9849]

Great explanation !! One question though, Any specific reason to use sets? The solution works with lists as well. If anyone have any idea, do let me know.

[@NeetCode]

Mainly because checking if a value exists in a HashSet is O(1) time, but with a list it's O(n).

[@prafulparashar9849]

@@NeetCode Thanks for clarifying, makes so much sense now to use a set in case of these scenarios.