N-Queens - Backtracking - Leetcode 51 - Python
HTML-код
- Опубликовано: 30 июл 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/n-queens
0:00 - Read the problem
3:56 - Drawing Explanation
12:27 - Coding Explanation
leetcode 51
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#backtracking #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. 
Наука
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
I love so much the idea of using posDiag set and negDiag set. That is the truly brilliant trick.
Right? It truly is fascinating
It's so good, who even comes up with these!
@@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.
truly
I was fascinated. How can one even think of this!
Backtracking never been this easy after watching your video! Thanks for the excellent intuition about backtracking.
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.
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.
This is the best video on backtracking I've seen so far. It was so good that I applauded after watching it.
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.
You explain difficult to understand concepts with amazing clarity, thank you for your work!
Amazing, I've seen a couple other variant, but this version is easy, yet really captures the spirit of backtracking without hard to understand tricks
Easily the best explanation on the internet thank you so much for your contributions :)
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. ❤
I can't express how this explanation blew my mind! You're the best, thank you.
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!
My best explanation of n-queens problem. Thank you!
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)
I have been watching several videos on n-queen, your video is the most understandable
Thanks, happy it was helpful! 😃
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.
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
I learnt something from this video. You explained it very clearly and concisely. Thank you!
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.
Shortest and best solution I have even seen. Thank you @Neetcode
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
@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.
very clever approach using negative and positive diagonals.. thx a lot for sharing!
This is the most cleanest approach to this problem, specially using sets to check Validity
Awesome solution, you simplified what I was trying to do greatly
Best explanation I have seen. Thanks!!!
Superb explanation as usual. Calm and thought out.
Very helpful! Very clear with explanation in coding as well. You are the best mentor in my learning way!
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.
Great explanation!!! Keep it up, neetcode!
Thanks for this amazing explanation. Loved it! 😍
Thanks for speaking clearly...was able to watch this on 2x
Much needed ❤️
I wish i could break down things as elegantly as u do in ur videos!!
Thank You So Much for this amazing Explanation!!
great, this helped me optimize my otherwise lengthy solution.😍
this is the best explanation i've found so far
Thanks for the content bro
Hi NeetCode, thank you for the amazing explanation
Brilliant solution; I learned a lot from the whole concept of (r+c) and (r-c); really great learning content.
You are a blessing to this world!
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
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.
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?
OMG that diagonal intuition 🤐
Respect ++ Sir!
Thanks! :)
Great explanation, thank you very much!
wow, you nailed it. Thanks a lot
Your explanations are amazing.
Thank you so much again!
the posDiag and the negDiag set is pretty clever. Makes the code so much more concise.
Great video!
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.
thank you this was very helpful
For those who confused what's the purpose of backtrack(0) code, it's basically call the backtrack function starting at row 0
Excellent explanation!
Simply the best :)
Such an elegant solution!
Great explaination ...Love from Nepal
Hope you upload more videos
pretty genius way to detect collision of diagonal!!
Amazing Explanation..💥
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?
This solution is elegant and ingenious. 🤩🤩
Best explanation yet!
Man you are awsome. Really awesome.
Just brilliant :)
What is the time complexity of this solution?
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
thank you so much youre a hero!
No!!! he's a super hero !
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?
One Question, Why can't we use regular variable instead of set to track posDiag and NegDiag, Since the values will be same.
the c on line 16 is actually presenting all the rows. Using 'c' is better for visualization
Hi Navdeep, Need a help ..how do u draw ? what tool u use ?
You Just Nailed the Power of Python.
This is art
Im getting an error on the part that we're trying to assing board[r][c] = "Q",
typerror: str object does not support item assignment
Does anyone got the same error?
Your videos are really great. May I know what is the significance of using a set.
I tried writing board = [['.']*n]*n, and rest all the exact same code, but it was giving the wrong output, why?
Amazing explaination
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).
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 "."?
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
The posDiag and negDiag solution is amazing!
You made this problem so easy :)
Glad it helped!
You are the best neet code
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).
What is the time and space complexity of the above solution ?
GOAT for a Reason!!!
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?
Great explanation
Just one word "Genius". What you know belongs to you what you can let other know that is the Talent. Kudos.
Thanks!
Hey Frank - thank you so much, I really appreciate it!! 😊
Why can't we do column - row for positive diagonal? It also gives 0 as constant value.
😱🤯excellent !!
awesome!
what is the time complexity for this?
Another masterpiece video on backtracking. Can you please make a video on Robot Room Cleaner | LEETCODE # 489?
genius solution. how do people have the insight to come up with this in anything less than a whole day
Great video :)(:
nice explanation sir
Finally its here
bro
thanks a lot
Backtrack is hard for me. I try to learn it by watching your videos