Whenever we want to generate all possible paths or answers, we need to think in terms of Recursion and Backtracking. Backtracking is simply undoing the change which we have already done. Summary: 1. We(mouse) are standing at (0,0) and we need to generate all possible paths so that the mouse reachers the last cell of the maze (n-1,n-1) 2. We are allowed to move in 4 directions only- Up, Down, Left and Right. We need to return a vector ans containing all possible paths through which the mouse can reach the end of maze. 3. Base conditions are pretty simple. Firstly, we cannot go beyond the boundaries of the matrix, secondly we cannot go to a cell which contains a blockage that is, matrix[i][j] denotes a blockage or wall and we cannot go through it. Also we need to mark every cell as visited with any other value(Fraz sir has marked with 0 for better understanding) such that we don't come back to the same cell again and again. Lastly, when we reach the target cell (n-1,n-1) we need to put our path string in ans[] vector and return as we have completed our objective. a) if(i =n) return; b) if(matrix[i][j] == 0) return; c) if(i==n-1 && j==n-1) { ans.push_back(path); return; } 4. Now, we have four options. But according to the problem we need to print the paths in sorted manner so we will move like- Down, Left, Right, Up. And before that we will mark the cell as visited by matrix [i][j] = 0 and Back-track at the end. // Mark as visited matrix[i][j] = 0; // Move Down help(i+1,j,path+'D'); // Move Left help(i,j-1,path +'L'); //Move Right help(i,j+1,path + 'R'); // Move Up help(i-1,j,path+'U); // Undo the change matrix[i][j] = 1; 5. Recursion will generate all the possible paths to reach end. We don't have to do anything else. Time Complexity: O(4^n*n) [ Because in worst case we will have a maze all filled with 1 and we will traverse all the cells to reach the end. And we have n*n cells in the maze and for each cell we have 4 option that's why Time Complexity is O(4^n*n) ] Space Complexity: O(n*n) [ This is equal to the height of the Recursive Tree and since we need to reach the end (n-1,n-1) from (0,0) that's why we need to traverse the entire matrix. ]
@@arghya_0802 I like your notes.Do you maintain notes for Babar DSA or any other series as well? Do you know when Fraz will start uploading DP videos? He is a great teacher.
🎯 Key Takeaways for quick navigation: 00:00 *🧩 Recursion Basics and Problem Introduction* - Recursion and backtracking explained as interconnected concepts. - Introduction to the maze problem where a rat needs to navigate through a grid to reach a destination. - Description of the maze grid structure and the objective of reaching a specific destination cell. 03:52 *🛤️ Understanding Recursive Approach to Maze Problem* - Explains how the maze problem is inherently recursive. - Describes the recursive nature of exploring all possible paths from a given position to the destination. - Emphasizes the need for systematically exploring all possible directions in the maze. 08:20 *🧭 Implementing Recursive Solution and Backtracking* - Details the recursive function for exploring paths in the maze. - Discusses the importance of backtracking to avoid revisiting already explored cells. - Demonstrates how to mark visited cells and backtrack to explore alternate paths. 10:25 *📊 Space and Time Complexity Analysis* - Analyzes the space complexity related to recursion, emphasizing the height of the recursion tree. - Explores the time complexity through the geometric progression of recursive calls. - Provides a breakdown of the number of nodes in the recursion tree to deduce the time complexity formula. 15:36 *💻 Coding the Recursive Solution* - Walks through the coding process of implementing the recursive solution in C++. - Demonstrates how to handle base cases, explore directions, mark visited cells, and backtrack. - Provides a step-by-step explanation of the code implementation.
Yesterday, I was visiting ur channel all the the time for next lecture Over recursion. I couldn't get next lecture then go for sleeping. Now just now I would see that one video would be uploaded on it. There's no any word to tell about ur consistency & dedication. Uh are a such down to earth man for students. Who don't have selfishness natural at all........God bless uh bhaiya!!......One thing it was most awaited video so far " RAT IN THE MAZE".......I will like to meet to uh once bhaiya!! Bhaiya.....I would complete all the questions of Contest 1 yesterday well.....Now am waiting for Contest 2!!
Notes: Similar problem to word search, gives us more confidence on how backtracking can be used to solve similar problems. Was able to do by making some changes in word search problem's code. T: O(4^(n * n)) S: O(n * n)
Episode 20 completed!! Rat in a maze Here, we will be given a rat and maze(matrix) and we need to find to find in how many paths the rat can reach the (n-1) (n-1) destination Here, the position in which rat can travel will be denoted by 1 and the positions which are prohibited are denoted by 0 1) Here, for each position we have four directions D, L, R, U so we can go in all these directions to reach the destination 2) So we will call recursive functions for all the four directions and ask recursion to do the next step 3) The base conditions are:- i and j cant go negative or out of the grid and if can't go to positions which are prohibited 4) And also we can travel through the position which we already travelled so while we are travelling we mark that position as 0 Time complexity:- O(4^n*n) Space complexity:- O(n*n) Once again amazing Explanation bhaiya!! 😍
Bro when I solve this question before your video came it kind of look confusing as I am not able to understand what they are trying to say by not using same cell again and agai again but when u solve it on board then I solve it in one time code before seeing ur code❤❤❤❤❤❤❤❤❤❤❤❤❤
Yesterday, I was visiting ur channel all the the time for next lecture Over recursion. I couldn't get next lecture then go for sleeping. Now just now I would see that one video would be uploaded on it. There's no any word to tell about ur consistency & dedication. Uh are a such down to earth man for students. Who don't have selfishness natural at all........God bless uh bhaiya!!......One thing it was most awaited video so far " RAT IN THE MAZE".......I will like to meet to uh once bhaiya!!
bro i was watching your previous videos and trying to solving those bro im didnt getting space and time complexity between two solution Combination ||| solution -1 ------------------------------------------- static void Solve(int ind,int k,int sum,int n,ArrayList ans,ArrayList ds){ if(ds.size()>=k){ if(sum==0){ ans.add(new ArrayList(ds)); } return; } if(ind==10)return;
![[LIVE] : ONE ลุมพินี 86 | คู่เอก "คมเพชร vs ชาติพยัคฆ์"](http://i.ytimg.com/vi/m3q_dRYDuU8/mqdefault.jpg)
![ปฏิเสธไม่ไหว (Crush on you) - LIPTA feat. No One Else [Official MV]](http://i.ytimg.com/vi/NBw1jF342vw/mqdefault.jpg)
Whenever we want to generate all possible paths or answers, we need to think in terms of Recursion and Backtracking. Backtracking is simply undoing the change which we have already done.
Summary:
1. We(mouse) are standing at (0,0) and we need to generate all possible paths so that the mouse reachers the last cell of the maze (n-1,n-1)
2. We are allowed to move in 4 directions only- Up, Down, Left and Right. We need to return a vector ans containing all possible paths through which the mouse can reach the end of maze.
3. Base conditions are pretty simple. Firstly, we cannot go beyond the boundaries of the matrix, secondly we cannot go to a cell which contains a blockage that is, matrix[i][j] denotes a blockage or wall and we cannot go through it. Also we need to mark every cell as visited with any other value(Fraz sir has marked with 0 for better understanding) such that we don't come back to the same cell again and again. Lastly, when we reach the target cell (n-1,n-1) we need to put our path string in ans[] vector and return as we have completed our objective.
a) if(i =n)
return;
b) if(matrix[i][j] == 0)
return;
c) if(i==n-1 && j==n-1)
{
ans.push_back(path);
return;
}
4. Now, we have four options. But according to the problem we need to print the paths in sorted manner so we will move like- Down, Left, Right, Up. And before that we will mark the cell as visited by matrix [i][j] = 0 and Back-track at the end.
// Mark as visited
matrix[i][j] = 0;
// Move Down
help(i+1,j,path+'D');
// Move Left
help(i,j-1,path +'L');
//Move Right
help(i,j+1,path + 'R');
// Move Up
help(i-1,j,path+'U);
// Undo the change
matrix[i][j] = 1;
5. Recursion will generate all the possible paths to reach end. We don't have to do anything else.
Time Complexity: O(4^n*n) [ Because in worst case we will have a maze all filled with 1 and we will traverse all the cells to reach the end. And we have n*n cells in the maze and for each cell we have 4 option that's why Time Complexity is O(4^n*n) ]
Space Complexity: O(n*n)
[ This is equal to the height of the Recursive Tree and since we need to reach the end (n-1,n-1) from (0,0) that's why we need to traverse the entire matrix. ]
Thanks I think 3.b)if(matrix[i][j] == 0) return; code is missed by Fraz in the video.
@@saurabhN1393 Welcome🤗
@@arghya_0802 I like your notes.Do you maintain notes for Babar DSA or any other series as well? Do you know when Fraz will start uploading DP videos? He is a great teacher.
@@saurabhN1393 No I only commented on Fraz sir's video. And I don't know when the series will get resumed😔
This Guy is Really Important to our Coding Community
Linked List Series was 💯💯
Ans now Recursion Series is going to be the Best one too!!
🎯 Key Takeaways for quick navigation:
00:00 *🧩 Recursion Basics and Problem Introduction*
- Recursion and backtracking explained as interconnected concepts.
- Introduction to the maze problem where a rat needs to navigate through a grid to reach a destination.
- Description of the maze grid structure and the objective of reaching a specific destination cell.
03:52 *🛤️ Understanding Recursive Approach to Maze Problem*
- Explains how the maze problem is inherently recursive.
- Describes the recursive nature of exploring all possible paths from a given position to the destination.
- Emphasizes the need for systematically exploring all possible directions in the maze.
08:20 *🧭 Implementing Recursive Solution and Backtracking*
- Details the recursive function for exploring paths in the maze.
- Discusses the importance of backtracking to avoid revisiting already explored cells.
- Demonstrates how to mark visited cells and backtrack to explore alternate paths.
10:25 *📊 Space and Time Complexity Analysis*
- Analyzes the space complexity related to recursion, emphasizing the height of the recursion tree.
- Explores the time complexity through the geometric progression of recursive calls.
- Provides a breakdown of the number of nodes in the recursion tree to deduce the time complexity formula.
15:36 *💻 Coding the Recursive Solution*
- Walks through the coding process of implementing the recursive solution in C++.
- Demonstrates how to handle base cases, explore directions, mark visited cells, and backtrack.
- Provides a step-by-step explanation of the code implementation.
Yesterday, I was visiting ur channel all the the time for next lecture Over recursion. I couldn't get next lecture then go for sleeping. Now just now I would see that one video would be uploaded on it. There's no any word to tell about ur consistency & dedication. Uh are a such down to earth man for students. Who don't have selfishness natural at all........God bless uh bhaiya!!......One thing it was most awaited video so far " RAT IN THE MAZE".......I will like to meet to uh once bhaiya!!
Bhaiya.....I would complete all the questions of Contest 1 yesterday well.....Now am waiting for Contest 2!!
Notes:
Similar problem to word search, gives us more confidence on how backtracking can be used to solve similar problems. Was able to do by making some changes in word search problem's code.
T: O(4^(n * n))
S: O(n * n)
Did the question by my own sir, thankyou so much for your recursion course. god bless you 😇
Thanks for amazingly simple solution 🙋🏻♂️🤗
Episode 20 completed!!
Rat in a maze
Here, we will be given a rat and maze(matrix) and we need to find to find in how many paths the rat can reach the (n-1) (n-1) destination Here, the position in which rat can travel will be denoted by 1 and the positions which are prohibited are denoted by 0
1) Here, for each position we have four directions D, L, R, U so we can go in all these directions to reach the destination
2) So we will call recursive functions for all the four directions and ask recursion to do the next step
3) The base conditions are:-
i and j cant go negative or out of the grid and if can't go to positions which are prohibited
4) And also we can travel through the position which we already travelled so while we are travelling we mark that position as 0
Time complexity:- O(4^n*n)
Space complexity:- O(n*n)
Once again amazing Explanation bhaiya!! 😍
Excellent lecture bro keep uploading we keep learning
Thank you for the efforts you put in and your consistency is incredible 🔥💫
Bhai aj me soch rha tha lecture nhi upload kiya......
Thank you bhai 😎
Aaega bro daily
Your explanation is dope
Bro when I solve this question before your video came it kind of look confusing as I am not able to understand what they are trying to say by not using same cell again and agai again but when u solve it on board then I solve it in one time code before seeing ur code❤❤❤❤❤❤❤❤❤❤❤❤❤
Great sir, Thank you❤🌹🙏
You are vrry hardworking bhiya 🥰❤
Extremely good content bro
Very good explanation
Thank you bhaiya
bhaiya when basic of programming language with dsa will launched . we are waiting .
Plz start beginners DSA course soon
We are waiting
Bro can you let me know what are you using to draw out things, I mean which digital pen?
very nice pls keep uploading videos. !
Thankyou so much bhaiya for your content.
Thanks I think if(matrix[i][j] == 0) return; code is missed by Fraz in the video.
Great bhaiya, thanks u so much🔥🔥❤❤
Thankyou bhaiya for this nice session
great video. Good explanation
👍🏻
Done understood ✅❤
thank you bhaiya for have a such good content.
want this video because I was having doubts
Reach++
When beginners DSA course will start
👍💯
Consistency++
Hey bro,, i am hare,😁😁 for u... 😍 thank.u bhAiya🥰
Thank you 🔥🔥
Episode 20 done!
Thanks for the video sir♥
#🥰🥰
Bro You are using c++ but i'm Java programmer how would I understand the DSA syntax
Did you understand the concept?
Maja Aggaya bhaiya
day 20
bohut zyada late ab kal dekhunga, abhi mood nahi hai 12 k baad padne ka
Yesterday, I was visiting ur channel all the the time for next lecture Over recursion. I couldn't get next lecture then go for sleeping. Now just now I would see that one video would be uploaded on it. There's no any word to tell about ur consistency & dedication. Uh are a such down to earth man for students. Who don't have selfishness natural at all........God bless uh bhaiya!!......One thing it was most awaited video so far " RAT IN THE MAZE".......I will like to meet to uh once bhaiya!!
How we will solve find the number of even numbers can be formed using the digits from 0 to 9 such that 3 and 5 are not adjacent.
Implement this using code.
In which language.. the solution of problem is coded?
ThnQ ones again
Fraz is better than didi and bhaiya who just rant I am for you.
codes kab aayenge
#include
void solve(vector&a,char ch,int x,int y,string &s,vector&ans,vector&d){
if(xa[0].size()-1||a[x][y]!=1||d[x][y]!=-1){
return;
}
if(x==a.size()-1&&y==a.size()-1){
s.push_back(ch);
ans.push_back(s);
s.pop_back();//backtracking is required to check different possible cases in a given question
return;
}
if(x==0&&y==0){
}
else{
s.push_back(ch);
}
d[x][y]=0;
solve(a,'L',x,y-1,s,ans,d);
solve(a,'R',x,y+1,s,ans,d);
solve(a,'D',x+1,y,s,ans,d);
solve(a,'U',x-1,y,s,ans,d);
s.pop_back();
d[x][y]=-1;
}
vector < string > searchMaze(vector < vector < int >> & arr, int n) {
// Write your code here.
vectord;
for(int i=0;i
bro i was watching your previous videos and trying to solving those
bro im didnt getting space and time complexity between two solution
Combination |||
solution -1
-------------------------------------------
static void Solve(int ind,int k,int sum,int n,ArrayList ans,ArrayList ds){
if(ds.size()>=k){
if(sum==0){
ans.add(new ArrayList(ds));
}
return;
}
if(ind==10)return;
ds.add(ind);
Solve(ind+1,k,sum-ind,n,ans,ds);
ds.remove(ds.size()-1);
Solve(ind+1,k,sum,n,ans,ds);
}
----------------------------------------------------------------------------
SOlution 2 :
static void Solve(int ind,int k,int sum,int n,ArrayList ans,ArrayList ds){
if(ds.size()>=k){
if(sum==0){
ans.add(new ArrayList(ds));
}
return;
}
for(int i=ind;i
Bro please help me
Consistency ++