L19. Rat in A Maze | Backtracking

[@takeUforward]

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

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

[@manvineekhra9291]

Why cannot it be solved by dynamic programming? Can't we store all path strings from a given cell?

[@vrashankraom]

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

[@ragul6356]

Indeed

[@verizon2851]

True!

[@asishcodes]

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]

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]

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

good observation!

[@juhisahu1360]

Hey, but in striver code also mouse is not visiting back to the cell from where it came as we are marking visited 1 so time complexity should be (3^n^2)

[@shashikantmony7844]

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]

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%

[@parthsalat]

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!

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

[@laxminarayanchoudhary939]

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.

[@navendraagrawal]

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]

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

[@navendraagrawal]

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 😂

[@amanbhadani8840]

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

[@rushidesai2836]

This should also be solved using a BFS. We can make a Queue. Data will have - Node, CurrentPath (List

[@chaitanyakumar9229]

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]

Can you explain it..a little more?

[@chaitanyakumar9229]

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

Modifying the input may not be allowed

[@chaitanyakumar9229]

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

[@sujan_kumar_mitra]

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

[@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🙏🙏..

[@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. :)

[@nimeykhurana1150]

vis is not required since we can block the previously traced path as-1 and while coming back(backtracking) it can again be restored to 1

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

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

[@PuranKaul]

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

[@parthsalat]

Complexity analysis: 16:50

[@loukikraina1783]

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]

Modifying input is considered as space only

[@loukikraina1783]

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

[@bhuvandahal421]

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

[@indycall1933]

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

[@mdaadilansari9055]

When we return back the string already doesn't have the last character(direction).

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

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

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]

thanks brother,, i also thought same way .

[@ShoyoHinata-ew4vn]

what if grid[i][j] is already 0 your code will change it to one

[@stith_pragya]

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

[@shivamtiwari3672]

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

[@rajansharma9066]

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.

[@bitbuybit9193]

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

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

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

[@shantipriya370]

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

[@Aryan-fi2qf]

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

[@adityan5302]

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

[@anandbabu9219]

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

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

[@vibhavsharma2724]

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

[@DurgaVinayBalla]

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.

[@FaisalKhan-oy4zz]

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]

No just clean code

[@FaisalKhan-oy4zz]

@@takeUforward Ty sir

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

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

[@pranavsharma7479]

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.

[@jacksparrow1316]

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

[@kamalsingh1345]

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

[@MotivateHours]

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

[@DivyaSingh-c3h]

One minor correction is we might end up going through (0,0) index again in some test cases because that is not marked as visited in the beginning.

[@shatranjKaKamaal]

Correct! We can just mark it as visited in the beginning itself.

[@mdfaizanmdfaizan6041]

You are a true gem the way you explain❤❤

[@talk2city212]

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]

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

[@talk2city212]

@@devisriprasad2021 Nahi bhai

[@nitinchandrasahu1774]

You can also do this without taking any extra matrix "visited", You can change the given "mat" matrix coordinate to 0 (as blocked), the path that the rat came from. By this, it will never check the path you came from and the TC will be O(3^(N^2)). Code 👇👇 class Solution { public: void solve(int row, int col, string path, vector &ans, vector mat) { int n = mat.size(); if(row==n-1 && col == n-1) { ans.push_back(path); return; } if(row0&&mat[row-1][col] == 1) { mat[row][col] = 0; solve(row-1, col,path + 'U', ans, mat); mat[row][col] = 1; } if(col0&&mat[row][col-1] == 1) { mat[row][col] = 0; solve(row, col-1,path + 'L', ans, mat); mat[row][col] = 1; } } vector findPath(vector &mat) { // Your code goes here vector ans; int n = mat.size(); //Rat can't enter if the entrance is blocked if(mat[0][0] == 1 && mat[n - 1][n - 1] == 1) solve(0, 0, "", ans, mat); return ans; } };

[@viraj701]

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

[@skilz9525]

got error bcoz of that only XD

[@mohitsingh7793]

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

[@indroneelgoswami5654]

The feeling after solving the question myself by just watching 6 minutes of the video is INSANE!!

[@prateeksomani5803]

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

[@Ace-ex9gg]

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

[@ayushjangid273]

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

[@sanketwakhare27]

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

[@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 ❤️❤️❤️❤️❤️‍🔥❤️‍🔥❤️‍🔥❤️‍🔥

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

[@tanayshah275]

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

[@takeUforward]

corrected..

[@wisdomkhan]

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!

[@percussionistbypassion2931]

The ultimate optimization is really outstanding.

[@dipeshdarji6253]

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

[@ajaybedre4199]

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

[@Roy0Anonymous]

Space Optimised Code O(1) [Ignoring recursion auxiliary space] class Solution{ public: vector findPath(vector &m, int n) { // Your code goes here vector ans; string s; if(m[0][0]==1) findPathUtil(m,n,ans,s,0,0); return ans; } private: void findPathUtil(vector &m, int n,vector& ans,string s,int i,int j) { if(i==n-1 && j==n-1) { ans.push_back(s); return; } m[i][j]=0; if(i-1>=0 && m[i-1][j]==1) { s.push_back('U'); findPathUtil(m,n,ans,s,i-1,j); s.pop_back(); } if(i+1=0 && m[i][j-1]==1) { s.push_back('L'); findPathUtil(m,n,ans,s,i,j-1); s.pop_back(); } if(j+1

[@garvitakbasantani5502]

Nice Solution, but could you please explain how you have handled lexicographic order?

[@RyanKOnk]

@@garvitakbasantani5502 sort the ans array/vector before returning.

[@deVamshi]

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

[@AbhishekKumar-yd7ls]

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

[@shivanshpatel1898]

class Solution { public: void move(int r,int c,vector &mat,string path,vector& ans,int n){ if(r==n-1 && c==n-1) { ans.push_back(path); return; } mat[r][c]=0; if( r+1=0 && mat[r][c-1]==1) move(r,c-1,mat,path+'L',ans,n); if( c+1=0 && mat[r-1][c]==1) move(r-1,c,mat,path+'U',ans,n); mat[r][c]=1; } vector findPath(vector &mat) { int n=mat.size(); vector ans; string path; if (mat[0][0] == 1) move(0,0,mat,path,ans,n); return ans; } };

[@goyal2662]

but where are we emoving the previous direction if it does not go to next part?

[@ADNANAHMED-eo5xx]

best tutorial on this topic on youtube

[@sidhantsuman4601]

no views but 5 likes and 3 comments wah re you tube

[@abhaybanerjee1074]

That is a glitch

[@bhavyajain9969]

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

[@ktsuw_217]

Amazing explanation! Thanks 😊

[@shreoshighosh5561]

please dont stop this series..

[@emazakhtar]

why use another matrix for marking visited , i did it with the input matrix and it worked

[@hitesh1800]

Bhai khudse toh solve ho hi nhi pata , video dekhna hi padta hai ur kuch dino mai wo bhi bhul jaata hu . Consistency hamesha break ho jata hai . Confidence build hi nhi hota guys mera upar se ab linkedn kholne se darr lagta hai . waha pr sab Codeforces,LC phodte jaa rahe hai guardian ,candidate master . Ab samjh nhi raha kya kru . koi thodi help kr sakta hai mere , college bhi tier 3 hai waha pr zyada log nhi hai , jo hai wo bhi zyada conisder nhi krte kyu ki woh bahut aayega nikal gaye hai

[@jasonbrody4618]

Instead of visited matrix , can't we use a variable that store from which direction we came from like we came from D-down so we shouldn't check U-up

[@jasonbrody4618]

Like check in string where we came from

[@gaurav4270]

cant this be solved using recursion code ,like the"NUMBER OF UNIQUE PATH IN GRID METHOD"

[@JaspreetChhabra]

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

[@ragul6356]

Where's the path where you actually run the code , I'm asking you this cuz I've been translating it to python actually and am facing an issue so

[@vegitogamingpubg3364]

Time complexity of the efficient solution?

[@sharmaji490]

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

[@PADALAVMANOJ]

So clean and smooth explanation Anna.

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

[@SPonharshitaP]

Please start string series with brute , better and optimal solutions

[@pleasantdayNwisdom]

pls tell me ...if without any btech degree ...i can get a job at faang ...i can learn whats needed from internet

[@anshumaan1024]

GFG pe segmentation fault a rha hai, first approach se class Solution{ // public: void solve(int i, int j, int n, string move, vector &arr, vector &vis, vector &ans){ if(i==n-1 && j==n-1 && arr[i][j]==1 ){ ans.push_back(move); return; } // downward if( i+1=0 && !vis[i][j-1] && arr[i][j-1]==1 ){ vis[i][j] = 1; solve(i,j-1,n,move+'L',arr,vis,ans); vis[i][j] = 0; } // right if( j+1=0 && !vis[i+1][j] && arr[i+1][j]==1){ vis[i][j] = 1; solve(i+1,j,n,move+'U',arr,vis,ans); vis[i][j] = 0; } } public: vector findPath(vector &m, int n) { vector vis(n, vector (n,0)); vector ans; if(m[0][0] = 1) solve(0,0,n,"",m,vis,ans); return ans; } };

[@vesperflix2211]

More clear code : class Solution{ private: vector ans; void dfs(int i, int j, vector&matrix, string str, int n){ // base case :: on last element of matrix if(i == n-1 && j == n-1){ ans.push_back(str); return; } // recurssive relation int delRow[] = {1,0,0,-1}; int delCol[] = {0,-1,1,0}; char delMove[] = {'D','L','R','U'}; for(int k=0;k=0) && (r=0) && (c

[@madhusreebera4472]

can't thank you enough for this course sir!

[@anmolsingh4026]

Very nicely done bro thanks 😁

[@takeUforward]

Thanks to you

[@mayankkashyap1893]

Does this code print all the possible path?

[@nikitakhandelwal6865]

My God I'm truly impressed!🔥

[@RamanDeep-es6or]

Thank you so much bhaiyaa ♥️💯

[@iamnottech8918]

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

[@Tomharry910]

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

[@PrashantSingh-jy6zp]

skip ads go to 3:43

[@amrendrabagga9124]

Hello Striver, Amazing explanation as always, but i have one doubt; time complexity should be (n*m)^4, as at every cell we are making 4 decisions. Instead of 4^(m*n)

[@your_name96]

nope, n*m cells have 4 choices each , i.e 4 * 4 * 4 ....n *m times hence the time complexity

[@sreenivasprasad6538]

@@your_name96 4^(N*M) should the time complexity

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

[@sagarmehla2102]

No need to take the new matrix for storing the visting , unvisting .

[@GauravJain-zo8gt]

striver is the messenger of GOD or he himself like a GOD. anant jai jinendra sir aapko

[@gouravkushwaha68]

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