L19. Rat in A Maze | Backtracking

Подписаться 605 тыс.

Просмотров 194 тыс.

50% 1

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
---------------------------------------------------------------------------------------------------------------------------------------------------- Pr-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: practice.geeksforgeeks.org/pr...
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

Опубликовано:

15 май 2021

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 287

@takeUforward 3 года назад

✅ Instagram: instagram.com/striver_79/ Please like and leave a comment if you understand, a comments means a lot to me :)

@ScienceSeekho Год назад

class Solution{ public: vector ans; void solve(int i, int j, vector &m, int n, string ds) { if(i < 0 || j < 0 || i >= n || j >= n || m[i][j] == 0) { // if we are beyond boundary / current is blocked = 0 return; } if(i == n-1 && j == n-1) { // If we reached the end ans.push_back(ds); ds = ""; return; } m[i][j] = 0; // set current visited so it wont picked up next time solve(i, j+1, m, n, ds + "R"); solve(i, j-1, m, n, ds + "L"); solve(i+1, j, m, n, ds + "D"); solve(i-1, j, m, n, ds + "U"); m[i][j] = 1; // backtrack it to 1 } vector findPath(vector &m, int n) { string ds = ""; if(m[0][0] == 0 || m[n-1][n-1] == 0) // If we cannot start at first position or end return {}; solve(0, 0, m, n, ds); return ans; } };

@memesdarbar6493 11 месяцев назад

Bro pls speak in hindi because sometimes I don't think what you tell.

@vrashankraom 3 года назад

Neither coding blocks nor coding ninjas courses worth rupees 10k can match this type of explanation. Hats off

@ragul6356 2 года назад

Indeed

@verizon2851 2 года назад

True!

@nopecharon 2 года назад

I have taken both the courses and believe me Striver, aditya verma and mycodeschool are just killing it. No paid content can compare to there approach of explaining

@karthikeyan1996_ Год назад

Scaler 3.5 lakhs u missed it bro

@ScienceSeekho Год назад

I did the 4K coding ninja course now watching this 🙂

@saketsharma133 Год назад

If anyone is wondering that in GFG the required TC is O(3^(N^2)). But here Striver has calculated it as O(4^(N^2)). Then, Striver has taken 4 choices at each point in matrix - D,L,R,U. But, in essence, there are only 3 choices. The place from where the mouse has came, it can not go back at that same place back. This eliminates 1 choice and leaves us with only 3 choices.

@immortal4412 Год назад

right perfect!

@sameeksha5309 9 месяцев назад

While backtracking, when I move to (3,1) from (3,2), the vis[3][2]=0, then how come we don't move back to (3,2) again since that position has been made unvisited during backtracking?

@shailesh_rajpurohit 3 месяца назад

@@sameeksha5309 because you are backtracking at the end of solve function from where you can not go to previously visted. Try to make a function tree and then you'll get it.

@ashtonronald 25 дней назад

good observation!

@shashikantmony7844 2 года назад

Thank you Striver, for the recursion series, I was really afraid of recursion, and the problems like Sudoku and N Queen used to haunt me. But not anymore. Thanks Striver

@elements8630 Год назад

Same

@iWontFakeIt 2 года назад

your explanation is so good that now i am writing code by myself, just watching the first 5-6mins of your video gives enough idea to approach the problem, though i am taking a bit longer to write the successful code, but writing it with my own understanding gives immense confidence to solve more! Thanks!!!

@saketsharma133 Год назад

Yes, absolutely right

@skilz9525 Год назад

can relate 100%

@skilz9525 Год назад

This series is absolute bonkers!!! U have taught us so well that just looking at first few minutes of the video I was able to solve this on my own without even looking at the pseudo code. Just cant thank you enough bro

@parthsalat 2 года назад

The best part is that he taught us the brute force solution and then optimised it! I'm gonna do the same thing in the interview!

@shinewanna3959 Год назад

After ur past tutorials, I did solve this problem by myself without watching the video, thanks to u for the best teaching. I love u bro. If u r right behind my side, I'll run towards u and will give u a big hug.

@fmkhandwala39 Год назад

After watching 18 videos so far, I was able to come up with the pseudo code myself for first time before watching the video. All because of your teaching. Cannot express in words my gratitude. Thank you!

@laxminarayanchoudhary939 2 года назад

Seriously, I really want to thank you from my heart for your efforts brother. Because after a break, i was thinking where to start for interview preparation and you are the one whose one of the video came up and I started following your series.

@amanbhadani8840 2 года назад

Loved your approach of solving questions,crisp and clear code.Enjoyed watching this recursion playlist.

@navendraagrawal 2 года назад

instead of using the visited vector we can also do m[i][j]=0 before another recursion call and m[i][j]=1 after that call

@suchitrandas7380 2 года назад

But that will alter the given matrix probably , isn't it?

@navendraagrawal 2 года назад

No while backtracking we can again set its value to be 1 so it will not alter the matrix

@ScienceSeekho Год назад

Yep. Thank me later. class Solution{ public: vector ans; void solve(int i, int j, vector &m, int n, string ds) { if(i < 0 || j < 0 || i >= n || j >= n || m[i][j] == 0) { // if we are beyond boundary / current is blocked = 0 return; } if(i == n-1 && j == n-1) { // If we reached the end ans.push_back(ds); ds = ""; return; } m[i][j] = 0; // set current visited so it wont picked up next time solve(i, j+1, m, n, ds + "R"); solve(i, j-1, m, n, ds + "L"); solve(i+1, j, m, n, ds + "D"); solve(i-1, j, m, n, ds + "U"); m[i][j] = 1; // backtrack it to 1 } vector findPath(vector &m, int n) { string ds = ""; if(m[0][0] == 0 || m[n-1][n-1] == 0) // If we cannot start at first position or end return {}; solve(0, 0, m, n, ds); return ans; } };

@techtsunami6814 Год назад

Senior sir aapko comments section mai dekh kar Khushi hui

@navendraagrawal Год назад

@@techtsunami6814 are bhai 🙏🙏 Lage raho bhai striver ki sari video dekh dalo 😂

@kishoregovindaraj7165 Год назад

Thank you Striver, for this amazing series. I had more confusions in recursion but this series made me feel, I can do the recursion problems easily.

@iamnehanupur Год назад

Thank you so much! I have been trying to understand this problem for a long time. Your explanation just made me understand the concept behind this problem.

@arkojeetbera8584 Год назад

We can just do the following: grid[i][j] = 0; ; grid[i][j] = 1; //-> backtrackin' step Yeah I know; many will disagree, saying we shouldn’t tamper with the original data, and I too agree with you as I abide by the same principle. But in this case if you see at the end, no cells are tampered, as we are replacing back the original values during the backtracking step. In my opinion, we can overlook the tamper factor as in this way we are not using another nxn auxiliary space (vis). Code: class Solution{ private: vector ans; void run(vector &grid, int n, int i=0, int j=0, string osf=""){ if(i=n || grid[i][j]==0) return; if(i==n-1 && j==n-1){ ans.push_back(osf); return; } grid[i][j] = 0; run(grid, n, i+1, j, osf+"D"); run(grid, n, i, j-1, osf+"L"); run(grid, n, i, j+1, osf+"R"); run(grid, n, i-1, j, osf+"U"); grid[i][j] = 1; //backtrackin' step } public: vector findPath(vector &m, int n) { run(m, n); return ans; } };

@iamnottech8918 4 месяца назад

I just thought the same and was wondering why he did'nt did that ,now i got it will will tamper the given data and i agree with you at the end it will just do the same and safe space

@ravikant1756 9 дней назад

thanks brother,, i also thought same way .

@kumaranuj03 Год назад

Thanks @takeUforward for this amazing playlist , Now I am able to think about the approach by my own.

@akshitmangotra5370 Год назад

Man I just love you alot. thanks for such beautiful entire series. I loved it so so so so sos much.. Even now I feel confident about Recursion. Earlier to I was like Bro.. what the topic is it. Thanks once again lot for this series.. Love you alot man for your efforts. :)

@bhuvandahal421 9 месяцев назад

I think this is easier to understand 😘🥰 // Rat in a Maze void mazeSolver(int row, int col, int& n, string& temp, vector& ans, vector& maze) { if(row == n - 1 && col == n - 1) { ans.push_back(temp); return; } maze[row][col] = 2; // Down if(row + 1 < n && maze[row + 1][col] == 1) { mazeSolver(row + 1, col, n, temp + "D", ans, maze); } // Left if(col - 1 >= 0 && maze[row][col - 1] == 1) { mazeSolver(row, col - 1, n, temp + "L", ans, maze); } // Right if(col + 1 < n && maze[row][col + 1] == 1) { mazeSolver(row, col + 1, n, temp + "R", ans, maze); } // Up if(row - 1 >= 0 && maze[row - 1][col] == 1) { mazeSolver(row - 1, col, n, temp + "U", ans, maze); } maze[row][col] = 1; }

@nagame859 Год назад

I watched all the recursive videos in this playlist. And the best thing is I solved this problem myself! Can't thank you more sir🙏🙏..

@chaitanyakumar9229 3 года назад

vis is not required, you can block the path ( put - 0) in curr posn and call solve fn then make it 1 again (backtracking)

@vaishnavisood9699 2 года назад

Can you explain it..a little more?

@chaitanyakumar9229 2 года назад

@@vaishnavisood9699 like use backtracking method (recursive way ) everytime you visit a cell, call a function for all the 4 neighbours, but as one of them is the cell that you are on at present, just mark it unreachable by marking it zero and after the 4 recursive calls make it 1 again !

@sujan_kumar_mitra 2 года назад

Modifying the input may not be allowed

@chaitanyakumar9229 2 года назад

@@sujan_kumar_mitra then you might use this, but in gfg and leetcode it was allowed to modify input

@sujan_kumar_mitra 2 года назад

@@chaitanyakumar9229 in online platform, it is allowed, but in interview, the interviewer might say that input cannot be modified (read about importance of immutability), so it's better to use separate visited array. But if space constraints are present, then we have to modify the input array

@Tomharry910 Год назад

This concludes me watching your recursion + backtracking series videos. It was very informative loaded with great explaination, plus it was fun to watch your videos. Many Many Thanks, Striver!

@shivamtiwari3672 2 года назад

Thanks striver, your videos are really helpful ,first time I wrote the whole code without seeing the video

@indycall1933 Год назад

Hi can anyone please explain why we didn't pop the last added char to the string while backtracking. Thanks in advance

@shashankarora2945 Год назад

I used to be afraid of recursion but now it is one of my strong topics and i am so proud of it thanks a lot striver sir

@sanketwakhare27 2 года назад

Thanks Striver for this wonderful video. Really helpful to understand. Keep up the great work!

@TheSketchbookSessions.656 Месяц назад

This " vis[0][0] =1 " should be done before calling the solve function. Otherwise compiler will come at (0,0) index again ,and that cause wrong output. Testcase for the above case is n=2 {{1,1},{1,1}}. In for loop approach.

@loukikraina1783 2 года назад

We can change the a[i][j] = 0, instead of using extra space for keeping visited blocks marked. Then after recursive call, change a[i][j] to the previous value (Backtracking).

@takeUforward 2 года назад

Modifying input is considered as space only

@loukikraina1783 2 года назад

@@takeUforward Ok Sir, Thank you for making such amazing videos.

@anandbabu9219 6 месяцев назад

you are one of my great teachers in my life thank you, you are younger than me you are helping me to under achieve my goals

@rajansharma9066 2 месяца назад

the cordinate is also important to decide where we go like when we go to Down then x=x+1, and y=y, similarly for other parts accordingly.

@vibhavsharma2724 2 месяца назад

Thank you striver for this great recursion series as now because of you only I can now able to build logic of my own. In this video also after watching the problem in first few minutes, I can able to solve the problem. Thank you...

@pranavsharma7479 2 года назад

bettr is not to use extra space just keep on marking the visited locations on the matrix and while backtracking make it as it was earlier.

@wisdomkhan 2 года назад

Wow, bhaiya, thanks to you that i did this almost by myself. I was right to keep faith in you and keep watching the videos and type the code. FInally!

@JaspreetChhabra 2 года назад

Best explanation so far !! Amazing. Thanks a lot :)

@bitbuybit9193 2 года назад

After understanding question i paused video and tries to solve it in my own.. and I solved it😍😍😍Pressed liked button..will start dp series from tomorrow

@deVamshi 2 года назад

You don't know how grateful i am for your content. Thank you very much!

@FaisalKhan-oy4zz 3 года назад

After truncating the *if part* will it reduce the time complexity? As we are not calling the function 4 times again!? Plz explain me.

@takeUforward 3 года назад

No just clean code

@FaisalKhan-oy4zz 3 года назад

@@takeUforward Ty sir

@kamalsingh1345 Год назад

Amazing playlist for recursion, Aag lga di bhaiya 💥💥💥💥💥💥💥💥👌

@sanketh768 Год назад

I think some cells will get visited more than once as per the code when we mark it unvisited so that the same cell will be picked by other recursive calls . Even the recursive tree says that the cell (2,1) is a part of 2 of the paths

@dom47 Год назад

when u back track even the visited cell becomes unvisited

@sanketh768 Год назад

@@dom47 so the TC cannot be O(Rows * columns) right? Like whenever it's given each cell can be visited only once I tend to calculate it like total no of cells

@MotivateHours 11 месяцев назад

Even it can be further optimized in terms of space complexity as we dont need to carry a Visited array just mark the 1of original given array to 0 and again 1 at the time of backtracking

@Aryan-fi2qf 2 года назад

I think you should put vis[0][0]=1 so that it doesn't travel twice through (0,0). In case of m=[[1,1],[1,1]] we shouldn't accept DURD, RLDR as correct ans right?

@abhisheksuryavanshi979 Год назад

Yes correct, Else we would get wrong answer for testcase 2 1 1 1 1 Changes-> if(m[0][0]==1){ vis[0][0]=true; findPathForRat(i,j,n,temp,m,ans,vis); }

@tasneemayham974 Год назад

I have two questions, Striver. Why didn't you remove the last character in the string when backtracking? And the second one is: Why are the directions like that? I mean if you are standing at m[0][0] and you want to go down, it's m[1][0], because you are increasing the rows, and staying at the same column right? It has nothing to do with the real x and y directions? THANK YOU FOR THE AMAZING CONTENT!!!!!!!!!!!!!!!!!

@Ace-ex9gg Год назад

it took me around 40min to solve this thing i guess. Solved it with that optimal approach itself.

@prateeksomani5803 2 года назад

Why don't you have passed string move by reference. I'm getting compilation error if I do that. And also you have not emptied the string s = "" after pushing the string to answer array. Please explain I'm confused here a bit

@Tomharry910 Год назад

Fantastic video. Great explaination of code and code logic. Thanks a ton!

@PuranKaul Месяц назад

why did we not mark the final element in vis at (n-1, n-1).

@arnabchakraborty246 2 года назад

Hatsss off.. Next level of Explanation.Thanks a lot bhaiyaa

@adityan5302 2 года назад

python solution : Refer only if you find difficulty in construction the code : class Solution: def findPath(self, arr, n): # code here res = [] vis = [[0 for i in range(n)] for j in range(n)] def solve(i, j, st=""): if i==n-1 and j==n-1: res.append(st) return # Downward if i+1=0 and arr[i][j-1] == 1 and vis[i][j-1] == 0: vis[i][j] = 1 solve(i, j-1, st+"L") vis[i][j] = 0 # Right if j+1=0 and arr[i-1][j] == 1 and vis[i-1][j] == 0: vis[i][j] = 1 solve(i-1, j, st+"U") vis[i][j] = 0 if arr[0][0]: solve(0, 0) return res

@jacksparrow1316 3 года назад

Its very helpful bro...plz dont stop.it💯♥️

@percussionistbypassion2931 Год назад

The ultimate optimization is really outstanding.

@pratikdas1780 Год назад

This question is pretty easy to solve if you're familiar with graphs. It's simple DFS+Backtracking. Also, try to solve Word Search alongside this problem, they're pretty similar.

@sakshipathak1855 Год назад

what if i use bfs?

@ktsuw_217 3 года назад

Amazing explanation! Thanks 😊

@DurgaVinayBalla 6 месяцев назад

I think there's no need of extra vis matrix. In my code I've put m[i][j] = 0 (blocked) and then unblocking it instead of vis matrix to know visited or not. it worked out fine. correct me if I'm wrong.

@parthsalat 2 года назад

Complexity analysis: 16:50

@udaytewary3809 Год назад

Really bhaiya u are goat this the time where I have written the recursion code in go without any error And whole credit goes to you bhaiya ❤️❤️❤️❤️❤️‍🔥❤️‍🔥❤️‍🔥❤️‍🔥

@shantipriya370 4 месяца назад

can someone explain why while we are back tracking, the string 'move' is not taken to its previous state?

@PADALAVMANOJ 8 месяцев назад

So clean and smooth explanation Anna.

@mohitsingh7793 Год назад

Time completxity : O(4^(N*N)) Space complexity :O(N*N)(visted-matrix) Auxilliary Space : O(N*N) Correct me I was wrong...

@roshanraj674 3 года назад

Thank you for explaining it beautifully

@stith_pragya 3 месяца назад

Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@viraj701 Год назад

don't forget to add vis[0][0]=1 before you go for recursion

@skilz9525 Год назад

got error bcoz of that only XD

@dipeshdarji6253 3 года назад

Can you please add time and space complexity analysis in your upcoming tutorial? It will be a great help.

@ajaybedre4199 2 года назад

Bro don't skip the video in between. He had explained time and space complexity in all the tutorial in this series, actually in this video also at 17.50

@aeroabrar_31 Год назад

@@ajaybedre4199 at 17:50

@vishnum7033 Год назад

sir your explanation is amazing as always , if(i=n || grid[i][j] ==0 || vis[i][j] ) return; if(i==grid.size()-1 and j==grid.size()-1) { ans.push_back(s); return; } vis[i][j] =1; solve(i+1,j,grid,s+"D",ans,vis); solve(i,j-1,grid,s+"L",ans,vis); solve(i,j+1,grid,s+"R",ans,vis); solve(i-1,j,grid,s+"U",ans,vis); vis[i][j] =0;

@AbhishekKumar-yd7ls 9 месяцев назад

I solved this without seeing the explanation. This whole series is awesome ❤

@mdfaizanmdfaizan6041 24 дня назад

You are a true gem the way you explain❤❤

@ItsGaganKhatri Год назад

thankyou Sir, I didnt knew Backtracking Earlier , after watching your video and solving them again myself... I WAS ABLE TO SOLVE THIS ONE WITHOUT ANY HELP #StriverOP

@madhusreebera4472 2 года назад

can't thank you enough for this course sir!

@shashankojha3452 3 года назад

Great Explanation!!!

@bhavyajain9969 Год назад

vis[0][0] should be assigned value 1 because it's treated as not visited thus, gives redundant and incorrect paths

@talk2city212 8 месяцев назад

in every loop of if we are approaching towards different position, then we should have mark that as visited. for example in first loop of downward: if(i+1 < n && !visited[i+1][j] && m[i+1][j]==1){ visited[i+1][j] = 1; dfs(m, n, visited, ans, temp+'D', i+1, j); visited[i+1][j] = 0; } if i am doing something wrong, please correct ......

@devisriprasad2021 5 месяцев назад

i too got the same doubt, did you figure it out?

@talk2city212 5 месяцев назад

@@devisriprasad2021 Nahi bhai

@shreoshighosh5561 3 года назад

please dont stop this series..

@ADNANAHMED-eo5xx 3 года назад

best tutorial on this topic on youtube

@iamnottech8918 4 месяца назад

Before watching the video the idea of solution was very clear in my head thanku for series

@RamanDeep-es6or 3 года назад

Thank you so much bhaiyaa ♥️💯

@vegitogamingpubg3364 3 года назад

Time complexity of the efficient solution?

@tanayshah275 3 года назад

@take U forward, c++ code link is messed up, great explanation btw.

@takeUforward 3 года назад

corrected..

@sharmaji490 3 года назад

Isn't it a recursion problem Backtracking would be when we need to find if any path exist and if yes then that path as well

@4BeTech 3 месяца назад

i did't comment usually but for this video i would say worth to being every single second here

@ayushjangid273 Год назад

how the character will be removed from the string 'move' when we backtrack ?

@akshatchaturvedi7407 3 года назад

🔥

@abhimanyu6534 3 года назад

Plz make more videos on concepts that you suggested in the cp video

@thefizzshow 2 года назад

Thanks Bro...This helped a lot.

@codeforthought1883 2 года назад

Bhai 1st half m hi samajh aa jata hai. Hats off

@anmolsingh4026 3 года назад

Very nicely done bro thanks 😁

@takeUforward 3 года назад

Thanks to you

@mayankkashyap1893 2 года назад

Does this code print all the possible path?

@Abhishek-yy3xg 3 года назад

Bhaiya, can u make an explanation video of Josephus problem.

@shastriamisha 2 года назад

Great explanation.. Thank you

@nikitakhandelwal6865 Год назад

My God I'm truly impressed!🔥

@gouravkushwaha3001 8 месяцев назад

Very easy problem..striver's explanation makes it more easier

@lovetocode 3 года назад

👍

@huzefataj7694 Год назад

Python code: def solve(i,j,a,n,ans,move,vis): if i==n-1 and j==n-1: ans.append(move) return # Down if i+1=0 and not vis[i][j-1] and a[i][j-1] == 1: vis[i][j]=1 solve(i,j-1,a,n,ans,move+'L',vis) vis[i][j]=0 #right if j+1=0 and not vis[i - 1][j] and a[i - 1][j] == 1: vis[i][j] = 1 solve(i-1,j,a,n,ans,move+'U',vis) vis[i][j]=0 ans=[] n=4 m=[[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 0, 0],[0, 1, 1, 1]] vis=[[0]*n for i in range(n)] if m[0][0]==1: solve(0,0,m,n,ans,"",vis) print(' '.join(ans)) ********************************************************************************************************* def solve(i,j,a,n,ans,move,vis,di,dj): if i==n-1 and j==n-1: ans.append(move) return dir='DLRU' for ind in range(n): nexti = i + di[ind] nextj = j + dj[ind] if nexti >= 0 and nextj >= 0 and nexti < n and nextj < n and not vis[nexti][nextj] and a[nexti][nextj] == 1: vis[i][j] = 1 solve(nexti, nextj,a,n,ans,move+dir[ind],vis,di,dj) vis[i][j] = 0 ans=[] n=4 m=[[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 0, 0],[0, 1, 1, 1]] di=[+1,0,0,-1] dj=[0,-1,1,0] vis=[[0]*n for i in range(n)] if m[0][0]==1: solve(0,0,m,n,ans,"",vis,di,dj) print(' '.join(ans))