@@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.
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 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)
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
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! 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.
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.
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!
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.
@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.
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).
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).
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)
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
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!)?
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
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! 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.
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.
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
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.
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
🚀 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 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 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 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 :)
I can't express how this explanation blew my mind! You're the best, thank you.
OMG that diagonal intuition 🤐
Respect ++ Sir!
Thanks! :)
Can't believe I solved this on my own (after 1.5 hours of thinking)!
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
You explain difficult to understand concepts with amazing clarity, thank you for your work!
My best explanation of n-queens problem. 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.
This is the most cleanest approach to this problem, specially using sets to check Validity
Thanks for speaking clearly...was able to watch this on 2x
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
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.
the posDiag and the negDiag set is pretty clever. Makes the code so much more concise.
For those who confused what's the purpose of backtrack(0) code, it's basically call the backtrack function starting at row 0
I learnt something from this video. You explained it very clearly and concisely. Thank you!
Just one word "Genius". What you know belongs to you what you can let other know that is the Talent. Kudos.
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.
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!
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?
Brilliant solution; I learned a lot from the whole concept of (r+c) and (r-c); really great learning content.
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.
very clever approach using negative and positive diagonals.. thx a lot for sharing!
Very helpful! Very clear with explanation in coding as well. You are the best mentor in my learning way!
Superb explanation as usual. Calm and thought out.
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.
Awesome solution, you simplified what I was trying to do greatly
Damn, the difficulty is in this diagonal trick, the backtracking itself is pretty straightforward.
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!
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!
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)
Best explanation I have seen. Thanks!!!
What do you eat man? Seriously, you make Backtracking problems look like a joke. Thanks for the solution!!
the c on line 16 is actually presenting all the rows. Using 'c' is better for visualization
This solution is elegant and ingenious. 🤩🤩
you are amazing! thank god this video exists! I am confused what the time complexity of this approach would be??
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!
The explanation was great! thanks
great, this helped me optimize my otherwise lengthy solution.😍
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!)?
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
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?
Much needed ❤️
Thanks for this amazing explanation. Loved it! 😍
Thank You So Much for this amazing Explanation!!
Your explanations are amazing.
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.
wow, you nailed it. Thanks a lot
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.
Thanks!
Hey Frank - thank you so much, I really appreciate it!! 😊
genius solution. how do people have the insight to come up with this in anything less than a whole day
Hi NeetCode, thank you for the amazing explanation
Backtrack is hard for me. I try to learn it by watching your videos
Great explanation!!! Keep it up, neetcode!
if you ask this question in an interview, you are what is wrong with the hiring process
true dat
GOAT for a Reason!!!
Such an elegant solution!
Great explanation, thank you very much!
Great explaination ...Love from Nepal
Hope you upload more videos
You are the best neet code
This ain't brute force, in brute force sol, you'd ITERATE and check if a queen is already placed at an attacking position
Thanks for the content bro
Amazing Explanation..💥
You made this problem so easy :)
Glad it helped!
thank you so much youre a hero!
No!!! he's a super hero !
Best explanation yet!
Excellent explanation!
Now ,i understood why channel name is Neetcode.
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
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.
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
Man you are awsome. Really awesome.
Great video!
Thank you so much again!
could you please also explain intuition behind TC ?
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😂😂
This question describes my romantic relationship with my four girlfriends perfectly. It's no surprise that it's hard.
This is art
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?