@@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.
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)
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.
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.
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.
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
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. ❤
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.
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.
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!
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
@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.
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.
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).
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)
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).
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
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😇
@@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
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?
Please always include time and space complexity for all solutions. My understanding is that interviewer always ask for time and space complexity in pretty much all interviews. Time O(N^N), Space O(N^2). I struggle with tighter time complexity for backtracking problems. If we can ignore previously visited locations from the search then it can actually be O(N!)?
Man, you gotta realize the diagonal trick. And then the n-tree instead of the 'true brute force'. BTW - true brute force was so hard to code. I ditched it and came here.
Java Solution: class Solution { public List solveNQueens(int n) { List res = new ArrayList(); HashSet col = new HashSet();HashSet pdiag = new HashSet(); HashSet ndiag = new HashSet(); char[][] board = new char[n][n]; for(int i=0;i
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.
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.
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
🚀 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 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.
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.
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.
Easily the best explanation on the internet thank you so much for your contributions :)
Can't believe I solved this on my own (after 1.5 hours of thinking)!
I can't express how this explanation blew my mind! You're the best, thank you.
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.
You explain difficult to understand concepts with amazing clarity, thank you for your work!
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
This is the most cleanest approach to this problem, specially using sets to check Validity
OMG that diagonal intuition 🤐
Respect ++ Sir!
Thanks! :)
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
My best explanation of n-queens problem. Thank you!
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. ❤
Thanks for speaking clearly...was able to watch this on 2x
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.
For those who confused what's the purpose of backtrack(0) code, it's basically call the backtrack function starting at row 0
Shortest and best solution I have even seen. Thank you @Neetcode
I learnt something from this video. You explained it very clearly and concisely. Thank you!
the posDiag and the negDiag set is pretty clever. Makes the code so much more concise.
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.
Just one word "Genius". What you know belongs to you what you can let other know that is the Talent. Kudos.
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!
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
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?
very clever approach using negative and positive diagonals.. thx a lot for sharing!
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.
@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 helpful! Very clear with explanation in coding as well. You are the best mentor in my learning way!
Awesome solution, you simplified what I was trying to do greatly
Superb explanation as usual. Calm and thought out.
Brilliant solution; I learned a lot from the whole concept of (r+c) and (r-c); really great learning content.
What do you eat man? Seriously, you make Backtracking problems look like a joke. Thanks for the solution!!
Damn, the difficulty is in this diagonal trick, the backtracking itself is pretty straightforward.
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.
this is the best explanation i've found so far
I wish i could break down things as elegantly as u do in ur videos!!
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).
You are a blessing to this world!
You Just Nailed the Power of Python.
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)
pretty genius way to detect collision of diagonal!!
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).
wow. simply fkn wow with the pos diag neg diag.. such a nice pattern to this.. holy moly. neet! 1337!!
The posDiag and negDiag solution is amazing!
the c on line 16 is actually presenting all the rows. Using 'c' is better for visualization
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
This solution is elegant and ingenious. 🤩🤩
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😇
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
@@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
I like this approach!
Best explanation I have seen. Thanks!!!
The explanation was great! thanks
genius solution. how do people have the insight to come up with this in anything less than a whole day
you are amazing! thank god this video exists! I am confused what the time complexity of this approach would be??
This ain't brute force, in brute force sol, you'd ITERATE and check if a queen is already placed at an attacking position
Backtrack is hard for me. I try to learn it by watching your videos
Much needed ❤️
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?
Please always include time and space complexity for all solutions. My understanding is that interviewer always ask for time and space complexity in pretty much all interviews.
Time O(N^N), Space O(N^2). I struggle with tighter time complexity for backtracking problems. If we can ignore previously visited locations from the search then it can actually be O(N!)?
if you ask this question in an interview, you are what is wrong with the hiring process
true dat
Your explanations are amazing.
Man, you gotta realize the diagonal trick. And then the n-tree instead of the 'true brute force'. BTW - true brute force was so hard to code. I ditched it and came here.
Thank You So Much for this amazing Explanation!!
Now ,i understood why channel name is Neetcode.
great, this helped me optimize my otherwise lengthy solution.😍
wow, you nailed it. Thanks a lot
Thanks for this amazing explanation. Loved it! 😍
Thanks!
Hey Frank - thank you so much, I really appreciate it!! 😊
Such an elegant solution!
Java Solution:
class Solution {
public List solveNQueens(int n) {
List res = new ArrayList();
HashSet col = new HashSet();HashSet pdiag = new HashSet();
HashSet ndiag = new HashSet();
char[][] board = new char[n][n];
for(int i=0;i
Super bro😂😂
You are the best neet code
GOAT for a Reason!!!
Excellent explanation!
Great explaination ...Love from Nepal
Hope you upload more videos
Great explanation!!! Keep it up, neetcode!
Amazing Explanation..💥
Best explanation yet!
Hi NeetCode, thank you for the amazing explanation
Thanks for the content bro
Me after seeing the problem: This is so hard what todo, how todo
After seeing the sol: This is the easiest question I've seen in my entire life
This question describes my romantic relationship with my four girlfriends perfectly. It's no surprise that it's hard.
This is art
Great video!
Great explanation, thank you very much!
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.
Mainly because checking if a value exists in a HashSet is O(1) time, but with a list it's O(n).
@@NeetCode Thanks for clarifying, makes so much sense now to use a set in case of these scenarios.
Why can't we do column - row for positive diagonal? It also gives 0 as constant value.
Great explanation
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?
thank you so much youre a hero!
No!!! he's a super hero !
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.
You made this problem so easy :)
Glad it helped!
My mind is blown
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
Thank you so much again!