@Striver sir, i think that this is even more efficient than your last solution class Solution { public: vector umap={-1,-1,-1,-1,-1,-1,-1,-1,-1}; bool is_safe(vector& vec,int row,int col,int n){ int i = 1; col--; while(col>=0){ if(umap[col]==-1 or umap[col]==row or umap[col]==row-i or umap[col]==row+i) return false; col--;i++; } return true; } void dfs(vector& res,vector&vec,int col,int n){ if(col==n){ res.push_back(vec); return; } for(int i = 0;i
Great explanation Striver, sometimes i wonder, when that day come to my life when i will be able to think like you while solving DSA problems like you did. You are real hero of my life. Hats off to you!
Hi Striver, Thanks a ton for your excellent videos.Honestly, I never thought i could solve all these hard problems or atleast understand them.But your explanation gave me the confidence and implanted a belief in myself that I too can solve problems.I will be forever grateful for your time and efforts kept in for teaching us.I hope you achieving everything that comes your way. Love you 3000❤
Ever since I started watching your videos, I always wondered yaar yeh itna achha kaise samjha sakte hai. Hats off to your explanation. This is just pure gods work.
Thank you for making the concept clear🤩. This playlist really helped me in leaning recursion and backtracking. I would really appreciate your efforts in making videos. YOU ARE TAKING ME FORWARD as the channel name suggests.
In the "isSafe" function if you pass the board by reference, execution speed increases quite a bit. Not Passing by reference : 74 ms Passing by reference : 6 ms
There is intuition to (n-1+col-row) as well, for every element of any matrix row-col and similarly col-row uniquely identifies the principal diagonal that element belongs to. In the worst case col can be 0 and row n-1 so we get -(n-1) , now this wouldn't be a problem if we were using map data structure but since we are using array we simply add (n-1) to the difference so that it starts from 0 and ends at index n-1+(n-1-0) = 2n-2 which is a total of 2n-1 elements.
That part where you explained why don't we need the check the placement of the queen was lit. It was a doubt since long time. Thanks for your explanation. ♥
For anyone trying to get the intuition behind the [n-1 + (col - row)] formula. I tried before watching that part, and I figured out that the values of (col - row) will range from -(n-1) , ..... 0 ...... , +(n+1) (total of 2n-1 values). So make a vector of that size. arr[0] has to represent n-1 . therefore to map the right index, the formula becomes (col-row) + n -1. Example: if n = 3, and (col-row) = -3, the hash of -3 has to be at the first index. -3 + (3-1) i.e, -3 + (n-1) will be 0. Hope I helped.
Little correction here, (col - row) will be -2 for n = 3 as row < n -> row < 3 so maximum low will be 2 for n = 3 and col will be zero and now -2 + (3 - 1) = 0
I was stuck on this one problem for months, because I didn't realize recursion is the choice to solve this problem. However even if I got the intuition of recursion, I might still have never solved this because I wasn't clear about the backtracking. You are a master of teaching, I never knew I would understand this and backtracking isn't as hard as I pictured it. Thank you
Bhai doing great work please continue doing what you are, you don't know how much help you're doing for the community. Mad respect and love❤️ Bhagwan tumhe zindagi mai kabhi kuch kam na padne de🙌
Watched other tutorials earlier too but watched this again. I must say I didn't find such good explanation with optimisation too. Thanks for the tutorial.
After 8th Lecture i have built up a great intution and tbh i have solved these problem on my own with your explanation. I can truly visualise the recursion now which i never did! Truly and amazing teacher you're!
Generally, I don't comment on any TH-cam videos, But after watching this precise explanation, I could not resist myself to give a comment. You literally change the HARD tag to the EASY one from your description.
Hi striver, for the upper diagonal check we can just use (row-col) as it is similar to the lower diagonal check rather than [(n-1)+(col-row)], Nice explanation though
When this question comes up, everyone tends to explain the questions rather that telling the approach and backtracking. Thank you boss for your amazing teaching technique.
Thanks a lot for Your wonderful Lectures which made me to solve the problems very much better than previously and Your Step by step Explanations were too enough to get understand the concepts, Once again Thank You.
according to me x-y=k and x+y=k are equations of diagonals so for any two queens queen1 and queen2 x[1]-y[1]!=x[2]-y[2] and x[1]+y[1]!=x[2]+y[2] and x[1]!=x[2] and y[1]!=y[2].
Awesome optimisations, farnkly I thought about one hashmap when I made my own theory of operations (I did through the row way where we iterate from column 0 to n-1) and I tracked all the columns with a hshmap, but the iteration was also nice that way the DS could be dropped but the diagonal ones need some hack.
Awesome tricks to overcome the problem of diagonals hash. by taking 2n-1 size of hash-set. for left diagonal (as implied in the video) = row+col and for right (we can even do) = col-row
Pure stormed explanation! Great one bro , keep going, please finish it within july, or if you have works , please tell us free resources from where the other problems can be learnt!
We can also do row - col for upper_diagonal and use negative values for hashing if you are using dictionaries' in python they can hold negative keys as well
I have seen countless Backtracking videos, but in all those videos it seemed like the teacher was trying to mug of the code. But yours is purely intution based hence understood better thank you.
Great Explanation. The first approach for isSafe() method is quite intuitive. But, I think it is difficult to come up with the second approach if you have not solved the question beforehand.
I can't believe in myself that after watching this explanation part only(without pseudo code) I write N-queen's java solution correct in 1 attempt. I am improving. All thanks to you.
class Solution: def solve(self,col,n,ans,board,leftRow,upperDiagonal,lowerDiagonal): # base case if col==n: ans.append(["".join(r) for r in board]) # looping through row to check if we can put the queen or not for row in range(n): if leftRow[row] == False and upperDiagonal[row+col] == False and lowerDiagonal[n-1+col-row] == False: board[row][col]='Q' leftRow[row]=True upperDiagonal[row+col] =True lowerDiagonal[n-1+col-row]=True # going for next col self.solve(col+1,n,ans,board,leftRow,upperDiagonal,lowerDiagonal) # backtracking step now put board[row][col]='.' leftRow[row]=False upperDiagonal[row+col] = False lowerDiagonal[n-1+col-row] = False def solveNQueens(self, n: int) -> List[List[str]]: # striver # declare a list to store the board ans = [] # declare the board row board = [["."] * n for _ in range(n)] # left row , upper diagonal, lower diagonal leftRow = [False for _ in range(n)] # why we have taken the size as 2*n-1 # because row+column = diagonal upperDiagonal= [False for _ in range(2*n-1)] lowerDiagonal=[False for _ in range(2*n-1)] self.solve(0,n,ans,board,leftRow,upperDiagonal,lowerDiagonal) return ans
In the recursion series, we have used backtracking right? in most of the questions in which when we come back we remove that particular element from ds.
Instagram for live updates about channel and live sessions: striver_79
Java explanation missing
@@raghurajan2167 this won’t be needing a Java explanation, just for loops used, hence you can see the cpp code and check the java code in description
@@raghurajan2167 Here you go - Shorter, intuitive code in Java
private void nQueenRecurse(int row, List positionStr, int n, List res,
List placements) {
if (n == row) {
res.add(new ArrayList(positionStr));
return; // backtrack
}
for (int col = 0; col < n; col++) {
placements.add(col);
if (isValidPlacement(row, placements)) {
// Build the locationString
StringBuilder qLocation = new StringBuilder(".".repeat(n));
qLocation.setCharAt(col, 'Q');
positionStr.set(row, qLocation.toString());
nQueenRecurse(row + 1, positionStr, n, res, placements);
}
placements.remove(placements.size() - 1);
}
}
private boolean isValidPlacement(int currentRow, List previousPlacements) {
for (int i = 0; i < currentRow; i++) {
int diff = Math.abs(previousPlacements.get(i) - previousPlacements.get(currentRow));
// Column Conflict & Diagonal conflict check
if (diff == 0 || diff == currentRow - i)
return false;
}
return true;
}
@Striver sir, i think that this is even more efficient than your last solution
class Solution {
public:
vector umap={-1,-1,-1,-1,-1,-1,-1,-1,-1};
bool is_safe(vector& vec,int row,int col,int n){
int i = 1;
col--;
while(col>=0){
if(umap[col]==-1 or umap[col]==row or umap[col]==row-i or umap[col]==row+i)
return false;
col--;i++;
}
return true;
}
void dfs(vector& res,vector&vec,int col,int n){
if(col==n){
res.push_back(vec);
return;
}
for(int i = 0;i
@@jalajyadav7074 nah, your safety checks more time, my one is o(1)
Finding previous Queens in just O(1) time was Amazing, learning so many things in Recursion!
😮
The Explanation is at God Level and Best on Internet, thank you.
Thanks Striver Vaiyaa for this premium class explaination .
U made this hard level problem looks very simple and easy .
Great explanation Striver, sometimes i wonder, when that day come to my life when i will be able to think like you while solving DSA problems like you did. You are real hero of my life. Hats off to you!
Thanks man, really appreciate your efforts
bhai 200 m kya hota h aaj kl 😂
@@RohitKumar-fy9fp showing respect and gratitude
@@RohitKumar-fy9fptm kitna diye ho bhai?
@@yashagarwal4388 kyu bhai tm kitna de diye .
@@RohitKumar-fy9fp haan toh kr de phir merko 200 , jb kuch nahi hota
Hi Striver,
Thanks a ton for your excellent videos.Honestly, I never thought i could solve all these hard problems or atleast understand them.But your explanation gave me the confidence and implanted a belief in myself that I too can solve problems.I will be forever grateful for your time and efforts kept in for teaching us.I hope you achieving everything that comes your way. Love you 3000❤
Hmmm... so recursion is the secret behind L's intelligence.
I'm going to tell Light about it!
That’s insane bruh! You explained it like a “Hello, world!” program. I owe you a big one.
Ever since I started watching your videos, I always wondered yaar yeh itna achha kaise samjha sakte hai.
Hats off to your explanation. This is just pure gods work.
This playlist is amazing! Never thought Backtracking would feel easy one day.
Perfect Explanation. When you explain hard question, those questions look like easy. Amazing.
Thank you for making the concept clear🤩.
This playlist really helped me in leaning recursion and backtracking.
I would really appreciate your efforts in making videos.
YOU ARE TAKING ME FORWARD as the channel name suggests.
In the "isSafe" function if you pass the board by reference, execution speed increases quite a bit.
Not Passing by reference : 74 ms
Passing by reference : 6 ms
after time optimization it was fast.
Yes this is because when we're not passing by reference, each time a new copy of board is created.
Very true !🤗
There is intuition to (n-1+col-row) as well, for every element of any matrix row-col and similarly col-row uniquely identifies the principal diagonal that element belongs to. In the worst case col can be 0 and row n-1 so we get -(n-1) , now this wouldn't be a problem if we were using map data structure but since we are using array we simply add (n-1) to the difference so that it starts from 0 and ends at index n-1+(n-1-0) = 2n-2 which is a total of 2n-1 elements.
nice one
excellent answer
Grt
Can you explain how it won’t be a problem if a map data structure is used?
@@SwapnilSarkar Because keys in a map data structure can be negative, but array indices can't be.
That part where you explained why don't we need the check the placement of the queen was lit. It was a doubt since long time. Thanks for your explanation. ♥
Man you give goosebumps every time i watch your videos. It's been long since I felt like this. Love you bro :)
For anyone trying to get the intuition behind the [n-1 + (col - row)] formula.
I tried before watching that part, and I figured out that the values of (col - row) will range from -(n-1) , ..... 0 ...... , +(n+1) (total of 2n-1 values). So make a vector of that size.
arr[0] has to represent n-1 . therefore to map the right index, the formula becomes
(col-row) + n -1.
Example: if n = 3, and (col-row) = -3, the hash of -3 has to be at the first index. -3 + (3-1) i.e, -3 + (n-1) will be 0.
Hope I helped.
but -3+(3-1) is -1 right?
Little correction here, (col - row) will be -2 for n = 3 as row < n -> row < 3 so maximum low will be 2 for n = 3 and col will be zero and now -2 + (3 - 1) = 0
I was stuck on this one problem for months, because I didn't realize recursion is the choice to solve this problem. However even if I got the intuition of recursion, I might still have never solved this because I wasn't clear about the backtracking. You are a master of teaching, I never knew I would understand this and backtracking isn't as hard as I pictured it.
Thank you
I'm just searching explanation of n-queens problem and hear is it 😂... thanks striver ❤
So nice of you
Thanks, Striver sir. This is the best explanation available for this problem.
Bhai doing great work please continue doing what you are, you don't know how much help you're doing for the community. Mad respect and love❤️
Bhagwan tumhe zindagi mai kabhi kuch kam na padne de🙌
Watched other tutorials earlier too but watched this again. I must say I didn't find such good explanation with optimisation too. Thanks for the tutorial.
Both educational and entertaining to watch 😃
After 8th Lecture i have built up a great intution and tbh i have solved these problem on my own with your explanation. I can truly visualise the recursion now which i never did! Truly and amazing teacher you're!
Generally, I don't comment on any TH-cam videos, But after watching this precise explanation, I could not resist myself to give a comment. You literally change the HARD tag to the EASY one from your description.
Hi striver, for the upper diagonal check we can just use (row-col) as it is similar to the lower diagonal check rather than [(n-1)+(col-row)], Nice explanation though
Exactly.
then you have to deal in -ve indexes
Explanation OP 🙌
Haha, thanks bro.. ache se pdhai kro :P
our teacher taught this as if it were a problem about theory of relativity and you taught it like the alphabet. thank you so much
Such a nice explanation!! loved it. The effort that you give to explain problem by writing down all the recursion tree is just unmatched.
When this question comes up, everyone tends to explain the questions rather that telling the approach and backtracking. Thank you boss for your amazing teaching technique.
I don't think on any platform there could be a better explanation to this problem than this one. Hat's off Striver !!!!
you have java code ?
If you think so, Neetcode's solution for N-queens is much more efficient, better and concise.
Oh! my goodness what an explanation about hashing and storing the values. Making it optimised.
owesome owesome!!!!!!
You are the best teacher one can have. The pride of our college ❤
Thanks a lot for Your wonderful Lectures which made me to solve the problems very much better than previously and Your Step by step Explanations were too enough to get understand the concepts, Once again Thank You.
What an explanation! Amazing! N-Queens has never seemed so easy before!
I've been searching for the good explanation then I found yours that's amazing thanks great work.
please please complete this series before July. your content is better than paid content.
Tab itna kam kyu dekhte ho XD
@@takeUforward kyuki indians ko uski chiz ki kadar hoti h jismein unke paise lag rhe ho
@@ishankbansal9239 Sahi baat h, islie sb paid ho raha hai...
@@Tarunkumar_Gatla bro jo bhi channel agr kuch bhi padha rha hoga na uss par hamesha kam hi views aate h
according to me x-y=k and x+y=k are equations of diagonals so for any two queens queen1 and queen2 x[1]-y[1]!=x[2]-y[2] and x[1]+y[1]!=x[2]+y[2] and x[1]!=x[2] and y[1]!=y[2].
Thanks for this
One of the most famous problems of all time. You made it look easy.
For upper diagonal (row-col) will be same... we can use that instead of (n-1 + col - row) in hashing approach.
Best instructor on TH-cam. Explains step by step
Awesome optimisations, farnkly I thought about one hashmap when I made my own theory of operations (I did through the row way where we iterate from column 0 to n-1) and I tracked all the columns with a hshmap, but the iteration was also nice that way the DS could be dropped but the diagonal ones need some hack.
Awesome tricks to overcome the problem of diagonals hash.
by taking 2n-1 size of hash-set.
for left diagonal (as implied in the video) = row+col
and for right (we can even do) = col-row
I did the same, but with row+col and row-col.
Hashing Part was something , I could have never think of. Thanks.
This series is too op ! Can u also prepare a sheet or hint video about how to prepare for coding rounds ?
Google striver’s cp sheet
BEST EXPLANATION ON INTERNET EVER !!!! WONDERFULL AND INDEPTH EXPLANATION!!!
You have taught so well!!
Recursion feels so easy now, thank you so much for your efforts🙏
Striver I am from West Bengal. You are god of problem solving!! ❤❤❤❤❤❤
Liked even before watching. That's your quality bro ! Top notch👌
If someone don't know dsa, it is still understandable
Just because of your Brillant Explanation !
Brilliant!! No one would have made me understand n-queen better than this👏👏
Pure stormed explanation! Great one bro , keep going, please finish it within july, or if you have works , please tell us free resources from where the other problems can be learnt!
We can also do row - col for upper_diagonal and use negative values for hashing if you are using dictionaries' in python they can hold negative keys as well
This is God Level Explanation ! Thankyou Soo Much !
Finding previous queens in constant time was great man!!!!
I was trying to decrease the space complexity for the previous queen from O(3n) to O(n), but then striver be like why not O(1) instead. Brilliant.
I have seen countless Backtracking videos, but in all those videos it seemed like the teacher was trying to mug of the code. But yours is purely intution based hence understood better thank you.
Thanks a lot!! I don't think this can be explained any better.
That kind of optimization is damn good!!! This is next level and that explanation... I have no words to say.. fab work bhaiya🤠🤠
Best channel for data structures and algorithms, No one can ever match the content and explanation🤗
I watched the same question on Aman Dhattarwal's channel. I must say that the way you explained it, it now looks like a piece of cake to me
Very beautiful and simple to understand explainaton and code. Thank you so much!
Striver bro u are just 🔥🔥🔥🔥🔥🔥🔥🔥 ... The best solution I have ever seen on youtube.....
Great Explanation. The first approach for isSafe() method is quite intuitive. But, I think it is difficult to come up with the second approach if you have not solved the question beforehand.
I thought of left row hashing by myself....but diagonal one was just insane..striver🔥
Take U forward is turu lob ❤️
I can't believe in myself that after watching this explanation part only(without pseudo code) I write N-queen's java solution correct in 1 attempt. I am improving. All thanks to you.
if u know chess: 7:00
code walkthru: 19:45
came here to look for optimized solution of N Queens xD after the 72+ offers video, Thanks for the optimization man, You are great!
0:01 I hope you're also doing extremely well ❤
Mannnnn....This is just amazing and the simplest explanation. Great work Striver bhai
hi striver....what is the time and space complexity for efficient solution?
Actually i watched 2 times other videos but cant understand but strivers i just seen 1 time understood clearly
Tq tq tq striver
just one word for this level of explanation!! LEGEND!!🙌
class Solution:
def solve(self,col,n,ans,board,leftRow,upperDiagonal,lowerDiagonal):
# base case
if col==n:
ans.append(["".join(r) for r in board])
# looping through row to check if we can put the queen or not
for row in range(n):
if leftRow[row] == False and upperDiagonal[row+col] == False and lowerDiagonal[n-1+col-row] == False:
board[row][col]='Q'
leftRow[row]=True
upperDiagonal[row+col] =True
lowerDiagonal[n-1+col-row]=True
# going for next col
self.solve(col+1,n,ans,board,leftRow,upperDiagonal,lowerDiagonal)
# backtracking step now put
board[row][col]='.'
leftRow[row]=False
upperDiagonal[row+col] = False
lowerDiagonal[n-1+col-row] = False
def solveNQueens(self, n: int) -> List[List[str]]:
# striver
# declare a list to store the board
ans = []
# declare the board row
board = [["."] * n for _ in range(n)]
# left row , upper diagonal, lower diagonal
leftRow = [False for _ in range(n)]
# why we have taken the size as 2*n-1
# because row+column = diagonal
upperDiagonal= [False for _ in range(2*n-1)]
lowerDiagonal=[False for _ in range(2*n-1)]
self.solve(0,n,ans,board,leftRow,upperDiagonal,lowerDiagonal)
return ans
bruh my frnd is a noob in programming but after seeing your explanation, he is saying that coding is so easy... you make lives beautiful dude
You made this problem look so easy, great explanation. Thanks a lot
Sir I have no words to explain how beautifully u explained this complex question with 2 approaches🙏🙏
plz striver bhaiya july end se pehle sare videos sde sheet ke upload kr dijiye. Placement mein bhut help mil jayega🙏
I think we don't require two hash lists for diagonals
It can be done using one hash list
best video ever on N queens sir
really proud of you !!!
Thank you for all the efforts striver. Very well explained.
What a Explanation!!! Simply Amazing!!
nice explanation. Is it possible to solve a problem like this in 30 mins when you have not solved the same before already?
Best Explanation...and Your Graph Series is 💥❤️
Best explanation! 🔥💯 complexity aur mention kar dete bhaiya..
Thank you, striver it's a wonderful explanation.
phenomenal explanation. Great teacher!
Seea lot of vidios but cannot understand.but after seeing your vidio i feel very easy
Without striver DSA not exist
Thanks A lot Striver this video is very useful to understand easily
Thanks a ton man can't thank you enough for explaining this concept beautifully
Understood! Super amazing explanation as always, thank you very much!!
@take U forward
bhaiya the c++ code which you wrote before using hashing is not running ...please tell if there is any problem in the non hashing code
At 15:42 , when we got one ans in the 2nd column , while backtracking why we did not check for the right side of the 2nd recursive call box??
Should've explained one of the approaches in Java .. would've helped sir
Could you please tell the time and space complexities of both the approaches?
Very good explanation! Got the intuition. Thnx bhaiya.
In the recursion series, we have used backtracking right? in most of the questions in which when we come back we remove that particular element from ds.
Awesome explanation!!! Thank you very much!!!
Did it my self !!! felt amazing.
One of the best explanation for N Queeen Problem
Love u bhaiya ❤