L14. N-Queens | Leetcode Hard | Backtracking
Вставка
- Опубліковано 22 сер 2024
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- Pre-Requisites: Recursion Playlist Videos, watch at 1.25x for best experience.
✅Coding Ninjas Discount Link: aff.codingninj...
Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
Problem Link: leetcode.com/p...
C++/Java Code: takeuforward.o...
---------------------------------------------------------------------------------------------------------------------------------------------
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFam...
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: bit.ly/tufteleg... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #striver #placements
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!
😮
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!
The Explanation is at God Level and Best on Internet, thank 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!
Thanks Striver Vaiyaa for this premium class explaination .
U made this hard level problem looks very simple and easy .
That’s insane bruh! You explained it like a “Hello, world!” program. I owe you a big one.
I'm just searching explanation of n-queens problem and hear is it 😂... thanks striver ❤
So nice of you
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.
Man you give goosebumps every time i watch your videos. It's been long since I felt like this. Love you bro :)
Perfect Explanation. When you explain hard question, those questions look like easy. Amazing.
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. ♥
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
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.
Thanks, Striver sir. This is the best explanation available for this problem.
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?
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!
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
Both educational and entertaining to watch 😃
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.
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.
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🙌
You are the best teacher one can have. The pride of our college ❤
Striver I am from West Bengal. You are god of problem solving!! ❤❤❤❤❤❤
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.
Generally, I don't comment on any UA-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.
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 !🤗
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.
One of the most famous problems of all time. You made it look easy.
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
Explanation OP 🙌
Haha, thanks bro.. ache se pdhai kro :P
Oh! my goodness what an explanation about hashing and storing the values. Making it optimised.
owesome owesome!!!!!!
Thanks you so much sir
What an explanation! Amazing! N-Queens has never seemed so easy before!
Take U forward is turu lob ❤️
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...
@@takeUforward Indians ko bas roadmaps Chahiye isliye babbar ke channel pe itne views aate h aur aapkee channel me itne kam
@@Tarunkumar_Gatla bro jo bhi channel agr kuch bhi padha rha hoga na uss par hamesha kam hi views aate h
Such a nice explanation!! loved it. The effort that you give to explain problem by writing down all the recursion tree is just unmatched.
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.
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.
Hashing Part was something , I could have never think of. Thanks.
Best instructor on UA-cam. Explains step by step
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
Liked even before watching. That's your quality bro ! Top notch👌
BEST EXPLANATION ON INTERNET EVER !!!! WONDERFULL AND INDEPTH EXPLANATION!!!
Brilliant!! No one would have made me understand n-queen better than this👏👏
Thanks a lot!! I don't think this can be explained any better.
Amazing Mate 👍🏻
Finding previous queens in constant time was great man!!!!
If someone don't know dsa, it is still understandable
Just because of your Brillant Explanation !
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
if u know chess: 7:00
code walkthru: 19:45
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
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.
This is God Level Explanation ! Thankyou Soo Much !
You have taught so well!!
Recursion feels so easy now, thank you so much for your efforts🙏
JAVA guys 🤪
0:01 I hope you're also doing extremely well ❤
That kind of optimization is damn good!!! This is next level and that explanation... I have no words to say.. fab work bhaiya🤠🤠
Striver bro u are just 🔥🔥🔥🔥🔥🔥🔥🔥 ... The best solution I have ever seen on youtube.....
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.
Hashing technique just blew my mind.Thanks striver for these amazing videos
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.
came here to look for optimized solution of N Queens xD after the 72+ offers video, Thanks for the optimization man, You are great!
Best channel for data structures and algorithms, No one can ever match the content and explanation🤗
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!!🙌
Very beautiful and simple to understand explainaton and code. Thank you so much!
Mannnnn....This is just amazing and the simplest explanation. Great work Striver bhai
phenomenal explanation. Great teacher!
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
leetcode: marks the que as hard
striver : its simple ,its very very simple
For upper diagonal (row-col) will be same... we can use that instead of (n-1 + col - row) in hashing approach.
Everyone is a lion until the real lion arrives, Striver!
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!
I loved the Explanation, and the Hashing optimization was just too good !
Seea lot of vidios but cannot understand.but after seeing your vidio i feel very easy
Without striver DSA not exist
maaannn !! the optimization of the problem is totally lit 🔥🔥. after watching the first solution and understanding that solution never thought about hashing techinque here 💯
Avengers.. Assemble
Hotel..trivago
DSA..STRIVER. 😅❤
Yes, You are taking me forward.
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
You made this problem look so easy, great explanation. Thanks a lot
One of the best explanation for N Queeen Problem
Love u bhaiya ❤
plz striver bhaiya july end se pehle sare videos sde sheet ke upload kr dijiye. Placement mein bhut help mil jayega🙏
wooooowwwwwwww it was the best vdo for N-queens in whole internet so far...
Best Explanation...and Your Graph Series is 💥❤️
Thanks A lot Striver this video is very useful to understand easily
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🔥
Bhaisahab the third approach just blew my mind. Striver bhai you really bring change.
Thank you, striver it's a wonderful explanation.
Best explanation! 🔥💯 complexity aur mention kar dete bhaiya..
Your explanations are always simple and easy to understand.
Glad you think so!
Thanks a ton man can't thank you enough for explaining this concept beautifully
Striver >>>> any random bhaiya who knows how to copy paste codes.
Very good explanation. Great work.
What a Explanation!!! Simply Amazing!!
this was just awesome experience :)
Brother 3 month recursion ke karan depression me tha aapne bahar nikala.Thank you so much!!!.
Understood! Super amazing explanation as always, thank you very much!!