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; } };
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
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.
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?
@@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.
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)
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
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!!!
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.
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!
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
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.
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; } };
@@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 !
@@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
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); }
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).
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; } };
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
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.
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. :)
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.
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
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!
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.
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 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
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
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...
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
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; } };
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!!!!!!!!!!!!!!!!!
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?
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
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))
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 ❤️❤️❤️❤️❤️🔥❤️🔥❤️🔥❤️🔥
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 ......
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
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
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.
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; }
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
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
✅ Instagram: instagram.com/striver_79/
Please like and leave a comment if you understand, a comments means a lot to me :)
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;
}
};
Bro pls speak in hindi because sometimes I don't think what you tell.
Why cannot it be solved by dynamic programming? Can't we store all path strings from a given cell?
Neither coding blocks nor coding ninjas courses worth rupees 10k can match this type of explanation. Hats off
Indeed
True!
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
Scaler 3.5 lakhs u missed it bro
I did the 4K coding ninja course now watching this 🙂
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.
right perfect!
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?
@@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.
good observation!
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)
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
Same
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!!!
Yes, absolutely right
can relate 100%
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!
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.
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!
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
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.
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
But that will alter the given matrix probably , isn't it?
No while backtracking we can again set its value to be 1 so it will not alter the matrix
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;
}
};
Senior sir aapko comments section mai dekh kar Khushi hui
@@techtsunami6814 are bhai 🙏🙏
Lage raho bhai striver ki sari video dekh dalo 😂
This should also be solved using a BFS. We can make a Queue. Data will have - Node, CurrentPath (List
Loved your approach of solving questions,crisp and clear code.Enjoyed watching this recursion playlist.
vis is not required, you can block the path ( put - 0) in curr posn and call solve fn then make it 1 again (backtracking)
Can you explain it..a little more?
@@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 !
Modifying the input may not be allowed
@@sujan_kumar_mitra then you might use this, but in gfg and leetcode it was allowed to modify input
@@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
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🙏🙏..
Thanks @takeUforward for this amazing playlist , Now I am able to think about the approach by my own.
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;
}
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.
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).
Modifying input is considered as space only
@@takeUforward Ok Sir, Thank you for making such amazing videos.
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;
}
};
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
thanks brother,, i also thought same way .
what if grid[i][j] is already 0 your code will change it to one
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.
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.
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. :)
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.
what if i use bfs?
Thanks striver, your videos are really helpful ,first time I wrote the whole code without seeing the video
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
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
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!
Complexity analysis: 16:50
Its very helpful bro...plz dont stop.it💯♥️
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.
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.
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
when u back track even the visited cell becomes unvisited
@@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
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
Hi can anyone please explain why we didn't pop the last added char to the string while backtracking. Thanks in advance
When we return back the string already doesn't have the last character(direction).
don't forget to add vis[0][0]=1 before you go for recursion
got error bcoz of that only XD
The feeling after solving the question myself by just watching 6 minutes of the video is INSANE!!
Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
You are a true gem the way you explain❤❤
it took me around 40min to solve this thing i guess. Solved it with that optimal approach itself.
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...
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
Amazing playlist for recursion, Aag lga di bhaiya 💥💥💥💥💥💥💥💥👌
The ultimate optimization is really outstanding.
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;
}
};
After truncating the *if part* will it reduce the time complexity?
As we are not calling the function 4 times again!?
Plz explain me.
No just clean code
@@takeUforward Ty sir
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.
Correct! We can just mark it as visited in the beginning itself.
Time completxity : O(4^(N*N))
Space complexity :O(N*N)(visted-matrix)
Auxilliary Space : O(N*N)
Correct me I was wrong...
I solved this without seeing the explanation. This whole series is awesome ❤
no views but 5 likes and 3 comments wah re you tube
That is a glitch
You don't know how grateful i am for your content. Thank you very much!
Thanks Striver for this wonderful video. Really helpful to understand. Keep up the great work!
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!!!!!!!!!!!!!!!!!
why did we not mark the final element in vis at (n-1, n-1).
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!
can someone explain why while we are back tracking, the string 'move' is not taken to its previous state?
please dont stop this series..
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?
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);
}
best tutorial on this topic on youtube
Can you please add time and space complexity analysis in your upcoming tutorial? It will be a great help.
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
@@ajaybedre4199 at 17:50
Amazing explanation! Thanks 😊
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))
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
❤️❤️❤️❤️❤️🔥❤️🔥❤️🔥❤️🔥
vis[0][0] should be assigned value 1 because it's treated as not visited thus, gives redundant and incorrect paths
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 ......
i too got the same doubt, did you figure it out?
@@devisriprasad2021 Nahi bhai
So clean and smooth explanation Anna.
@take U forward, c++ code link is messed up, great explanation btw.
corrected..
can't thank you enough for this course sir!
Very nicely done bro thanks 😁
Thanks to you
Does this code print all the possible path?
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;
}
};
Best explanation so far !! Amazing. Thanks a lot :)
Thank you so much bhaiyaa ♥️💯
Please start string series with brute , better and optimal solutions
Time complexity of the efficient solution?
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
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
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.
Thank you for explaining it beautifully
My God I'm truly impressed!🔥
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;
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
Nice Solution, but could you please explain how you have handled lexicographic order?
@@garvitakbasantani5502 sort the ans array/vector before returning.
Bhaiya, can u make an explanation video of Josephus problem.
Fantastic video. Great explaination of code and code logic. Thanks a ton!
Before watching the video the idea of solution was very clear in my head thanku for series
in this visited matrix is not necessary, we can simply do the same things on the matrix also.
In interviews its not a good practice
Very easy problem..striver's explanation makes it more easier
No need to take the new matrix for storing the visting , unvisting .
Bhai 1st half m hi samajh aa jata hai. Hats off
The optimization part was superb got lot more to learn
Hatsss off.. Next level of Explanation.Thanks a lot bhaiyaa
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
i did't comment usually but for this video i would say worth to being every single second here
striver is the messenger of GOD or he himself like a GOD. anant jai jinendra sir aapko
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
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;
}
};
is development important for faang or mastering dsa is enough?
both are equally important , do on alternative weaks !
Sir pls make video on geek collects the balls which is in greddy algorithm pls sir 🙏🙏
Thanks a lot for helping us. Just a suggestion, Bhai bahot lambe video banata h
Nai wo actually java and cpp dono code rhta na, and me thoda deep me explain krta islie lambe hote h
@@takeUforward Ur videos are 💖💖
but where are we emoving the previous direction if it does not go to next part?