L14. N-Queens | Leetcode Hard | Backtracking

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.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Pre-Requisites: Recursion Playlist Videos, watch at 1.25x for best experience.
✅Coding Ninjas Discount Link: aff.codingninjas.com/click?o=...
Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
Problem Link: leetcode.com/problems/n-queens/
C++/Java Code: takeuforward.org/data-structu...
---------------------------------------------------------------------------------------------------------------------------------------------
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse​
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse​
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily​
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / ​
✅ Instagram: / ​
✅Connect with us: bit.ly/tuftelegram​ (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa​ #striver #placements

[@takeUforward]

Instagram for live updates about channel and live sessions: striver_79

[@raghurajan2167]

Java explanation missing

[@takeUforward]

@@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

[@protyaybanerjee5051]

@@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; }

[@jalajyadav7074]

@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

[@takeUforward]

@@jalajyadav7074 nah, your safety checks more time, my one is o(1)

[@nishant3904]

Finding previous Queens in just O(1) time was Amazing, learning so many things in Recursion!

[@Piyush-yp2po]

😮

[@coding8000]

The Explanation is at God Level and Best on Internet, thank you.

[@akshatagarwal8125]

Thanks man, really appreciate your efforts

[@RohitKumar-fy9fp]

bhai 200 m kya hota h aaj kl 😂

[@nasim3987]

@@RohitKumar-fy9fp showing respect and gratitude

[@yashagarwal4388]

​@@RohitKumar-fy9fptm kitna diye ho bhai?

[@RohitKumar-fy9fp]

@@yashagarwal4388 kyu bhai tm kitna de diye .

[@063harshsahu2]

@@RohitKumar-fy9fp haan toh kr de phir merko 200 , jb kuch nahi hota

[@muhammedimdaad]

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

[@ryuzaki8142]

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❤

[@parthsalat]

Hmmm... so recursion is the secret behind L's intelligence. I'm going to tell Light about it!

[@ferozqureshi5228]

That’s insane bruh! You explained it like a “Hello, world!” program. I owe you a big one.

[@anupamdubey5736]

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. ♥

[@santhoshs7028]

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.

[@tanmayjain5821]

Such a nice explanation!! loved it. The effort that you give to explain problem by writing down all the recursion tree is just unmatched.

[@Mayanksingh-qp6dy]

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.

[@noobCoder26]

Thanks Striver Vaiyaa for this premium class explaination . U made this hard level problem looks very simple and easy .

[@cgoxo]

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.

[@ahanavishwakarma3956]

This playlist is amazing! Never thought Backtracking would feel easy one day.

[@sheharyarkhan5500]

Oh! my goodness what an explanation about hashing and storing the values. Making it optimised. owesome owesome!!!!!!

[@NithinjainKathadka]

Man you give goosebumps every time i watch your videos. It's been long since I felt like this. Love you bro :)

[@pavanmutalikdesai6611]

Perfect Explanation. When you explain hard question, those questions look like easy. Amazing.

[@rohitchanda8461]

What an explanation! Amazing! N-Queens has never seemed so easy before!

[@ayush.kumar_02]

I'm just searching explanation of n-queens problem and hear is it 😂... thanks striver ❤

[@takeUforward]

So nice of you

[@aradhyapandey1489]

You have taught so well!! Recursion feels so easy now, thank you so much for your efforts🙏

[@abhisheksa6635]

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.

[@abhishekshah581]

Generally, I don't comment on any KZbin 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.

[@KhsDorababu]

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.

[@aanchalmittal9897]

Brilliant!! No one would have made me understand n-queen better than this👏👏

[@virajasmane3416]

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🙌

[@amangaud3207]

Thanks, Striver sir. This is the best explanation available for this problem.

[@terabaap1775]

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

[@rohandsouza9147]

came here to look for optimized solution of N Queens xD after the 72+ offers video, Thanks for the optimization man, You are great!

[@atharvakulkarni2024]

BEST EXPLANATION ON INTERNET EVER !!!! WONDERFULL AND INDEPTH EXPLANATION!!!

[@ShravanKumar-lq7et]

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!

[@moonlight-td8ed]

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

[@anshumanpanigrahi7817]

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.

[@ananttyagi7372]

One of the most famous problems of all time. You made it look easy.

[@adityapandey4415]

Hashing Part was something , I could have never think of. Thanks.

[@nopecharon]

Best instructor on KZbin. Explains step by step

[@Tomharry910]

Very beautiful and simple to understand explainaton and code. Thank you so much!

[@suchithreddy733]

Mannnnn....This is just amazing and the simplest explanation. Great work Striver bhai

[@funshowsdh1yl]

Best channel for data structures and algorithms, No one can ever match the content and explanation🤗

[@rocksrust]

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!

[@arnabmondal81]

Striver I am from West Bengal. You are god of problem solving!! ❤❤❤❤❤❤

[@harshsuryawanshi3262]

I don't think on any platform there could be a better explanation to this problem than this one. Hat's off Striver !!!!

[@subhajitchoudhury4981]

you have java code ?

[@piyushraj6927]

If you think so, Neetcode's solution for N-queens is much more efficient, better and concise.

[@chakravarty-with-a-v]

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

[@vaibhavnayak3416]

after time optimization it was fast.

[@snehagoyal4978]

Yes this is because when we're not passing by reference, each time a new copy of board is created.

[@himanshu7271]

Very true !🤗

[@user-cj3zr7pu7t]

Thanks a lot!! I don't think this can be explained any better.

[@darshantawte7435]

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.

[@vegitogamingpubg3364]

You are the best teacher one can have. The pride of our college ❤

[@9-teen77]

can somebody please tell me what is the time complexity for the first solution and the second?

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@tanishagupta5668]

can anyone explain what is being added with the statement String s=new String(board[I]); res.add(s); as board is a multidimentional array and we get some reference by passing only one value

[@deveshlohumi7671]

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.

[@harshchoudhary4490]

nice one

[@ankitdubey9310]

excellent answer

[@arnabchakraborty246]

Grt

[@SwapnilSarkar]

Can you explain how it won’t be a problem if a map data structure is used?

[@deveshlohumi7671]

@@SwapnilSarkar Because keys in a map data structure can be negative, but array indices can't be.

[@dadidivya8663]

Amazing!!!! So So Soo Good! Understood... Thanks a lot for such a great content striver

[@sagargoyal6993]

Best Explanation...and Your Graph Series is 💥❤️

[@chetansahu1505]

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

[@TheDev05]

I did the same, but with row+col and row-col.

[@aratrikchandra1787]

Finding previous queens in constant time was great man!!!!

[@bablushaw6856]

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.

[@karapureddyjaswanthreddy6053]

can some explain how the any recursion call is ending without the col value is not reaching to "n" because we are stop the further recursion calls if we encouter that there is no position to fill?? how can we backtrack from that case and unmark the position??

[@aniketnangare904]

Thanks a ton man can't thank you enough for explaining this concept beautifully

[@anmolverma075]

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??

[@CostaKazistov]

Both educational and entertaining to watch 😃

[@tanishqtyagi1465]

That kind of optimization is damn good!!! This is next level and that explanation... I have no words to say.. fab work bhaiya🤠🤠

[@aakashyadav6228]

Liked even before watching. That's your quality bro ! Top notch👌

[@khatariinsaan5284]

If someone don't know dsa, it is still understandable Just because of your Brillant Explanation !

[@imajt5]

wow boss what an explaination...hats off to your effort. Thank you

[@karmanyaverma834]

This is God Level Explanation ! Thankyou Soo Much !

[@anushkathakur6531]

Could you please tell the time and space complexities of both the approaches?

[@dhanashreegodase4445]

hi striver....what is the time and space complexity for efficient solution?

[@rudra_anand]

You made this problem look so easy, great explanation. Thanks a lot

[@shivankkapila2954]

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

[@GeniuslyTensai]

Can someone please explain me how did bhaiya deduce the formula of [n-1]+[col-row] and how do we deduce such formulas for new questions

[@prikshit8]

please please complete this series before July. your content is better than paid content.

[@takeUforward]

Tab itna kam kyu dekhte ho XD

[@ishankbansal9239]

@@takeUforward kyuki indians ko uski chiz ki kadar hoti h jismein unke paise lag rhe ho

[@takeUforward]

@@ishankbansal9239 Sahi baat h, islie sb paid ho raha hai...

[@Tarunkumar_Gatla]

@@takeUforward Indians ko bas roadmaps Chahiye isliye babbar ke channel pe itne views aate h aur aapkee channel me itne kam

[@ishankbansal9239]

@@Tarunkumar_Gatla bro jo bhi channel agr kuch bhi padha rha hoga na uss par hamesha kam hi views aate h

[@riyasingla3841]

can someone pls explain the time complexity for both the approaches , shouldn't it be O(n!) for both the approaches !!

[@codewithakki4559]

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

[@himanshusoni1512]

Exactly.

[@krishnachandhok9998]

then you have to deal in -ve indexes

[@YashKumar-lo6ot]

Sir I have no words to explain how beautifully u explained this complex question with 2 approaches🙏🙏

[@AnandKumar-qj2iy]

so lovely explained😍😍...it can't be described in words!!!

[@iamnottech8918]

hey I want help where are first 2 rules that there are 1 row,1col with a queen i don't see them in q am I missing something or it is because of n*n ...

[@tirthpatel20]

For upper diagonal (row-col) will be same... we can use that instead of (n-1 + col - row) in hashing approach.

[@Rajat_maurya]

love u bhaiya love u...itta acche se kaise samjha lete ho

[@dikshacookinghub1414]

Very very good and easy explaination striver bro keep it up the good work

[@MohanaKrishnaVH]

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.

[@manistrikes]

I thought of left row hashing by myself....but diagonal one was just insane..striver🔥

[@raghavvohra8930]

board is a one-D vector how can we write board[row][col]??

[@K_EN_VisheshSaini]

Getting an error for n = 1 test case, why is it so? Someone explain please!

[@nikhilmadaan29]

just one word for this level of explanation!! LEGEND!!🙌

[@hmtg11]

@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

[@kartikeyasrivastava4798]

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].

[@giraffe4375]

Thanks for this

[@andreyvalverde4780]

Awesome explanation!!! Thank you very much!!!

[@rahulsihara8946]

Amazing Mate 👍🏻

[@srivatsaans6317]

Super Great brilliant explanation.. Really amazing work 🔥🔥🔥. Thanks for this amazing needful videos with the top notch explanation 👏

[@abhishekjaiswal6492]

can someone give me an idea about time as well as space complexity for both the approaches, please?

[@suyashjain3223]

What a Explanation!!! Simply Amazing!!

[@aniboy0071]

Can someone explain what is the time and space complexity in the later solution?

[@VisweshSuresh]

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.

[@aashish1206]

but -3+(3-1) is -1 right?

[@prithvirohira1372]

Thank you for all the efforts striver. Very well explained.

[@pankajsadhotra2316]

Bhaisahab the third approach just blew my mind. Striver bhai you really bring change.

[@shreyasingh1258]

Best explanation! 🔥💯 complexity aur mention kar dete bhaiya..

[@AnshuKumar-zn1qb]

Striver bro u are just 🔥🔥🔥🔥🔥🔥🔥🔥 ... The best solution I have ever seen on youtube.....

[@laxminarayanchoudhary939]

UNDERSTOOD , and Thank you so much bro....ANAND AA GAYA ||

[@PankajYadav-zg1re]

Kya gajab ka explanation hai thanks for being in our time....

[@joyjeetmukherjee8680]

Can anyone please tell me the T.C. and S.C. of optimized code?

[@bitturanjan9539]

Take U forward is turu lob ❤️

[@its_chirantan]

Very good explanation! Got the intuition. Thnx bhaiya.

[@sanskaarpatni9137]

Amazing solution using arrays as a hashset!