Ep20 - Rat in a Maze | Recursion | DSA series by Fraz | Notes available in description

[@ManikMahajan-b7x]

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

[@gigachad2419]

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

[@arghya_0802]

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

[@saurabhN1393]

Thanks I think 3.b)if(matrix[i][j] == 0) return; code is missed by Fraz in the video.

[@arghya_0802]

@@saurabhN1393 Welcome🤗

[@saurabhN1393]

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

[@arghya_0802]

@@saurabhN1393 No I only commented on Fraz sir's video. And I don't know when the series will get resumed😔

[@DPCODE72]

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

[@aryanraj728]

Thanks for amazingly simple solution 🙋🏻‍♂️🤗

[@vishalgowrav]

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!! 😍

[@chinmaypanchal2521]

Did the question by my own sir, thankyou so much for your recursion course. god bless you 😇

[@amiagarwal1083]

Thank you for the efforts you put in and your consistency is incredible 🔥💫

[@AtomicAkshay]

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)

[@gauravkumar3036]

Your explanation is dope

[@it_08amanagarwal35]

Excellent lecture bro keep uploading we keep learning

[@Shakib.Siddiqui]

Bhai aj me soch rha tha lecture nhi upload kiya...... Thank you bhai 😎

[@LearnYardYT]

Aaega bro daily

[@Lucifer-xt7un]

Extremely good content bro

[@AmitYadav-kr6vf]

Great sir, Thank you❤🌹🙏

[@CodeandColors22]

You are vrry hardworking bhiya 🥰❤

[@PRIYANSHUKUMAR-un9zu]

Great bhaiya, thanks u so much🔥🔥❤❤

[@HarshitSharma-si4wl]

Very good explanation

[@HarshitSharma-si4wl]

Thank you bhaiya

[@Ajaysingh-dg8pi]

Bro can you let me know what are you using to draw out things, I mean which digital pen?

[@it_08amanagarwal35]

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

[@Abhishek-fo3fc]

Done understood ✅❤

[@sanketbhagat1222]

Thankyou so much bhaiya for your content.

[@brijeshgaba5230]

bhaiya when basic of programming language with dsa will launched . we are waiting .

[@darshankalathiya8667]

very nice pls keep uploading videos. !

[@ranitbandyopadhyay]

great video. Good explanation

[@ratnasanjay]

Thankyou bhaiya for this nice session

[@kaifhasan8960]

thank you bhaiya for have a such good content.

[@emtiazahmed5333]

Hey bro,, i am hare,😁😁 for u... 😍 thank.u bhAiya🥰

[@chiragkarnwal6740]

Thanks for the video sir♥

[@aimanshaikh7201]

Plz start beginners DSA course soon We are waiting

[@sankalpgahlot6190]

Bro You are using c++ but i'm Java programmer how would I understand the DSA syntax

[@LearnYardYT]

Did you understand the concept?

[@rabindradocument8934]

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.

[@rabindradocument8934]

Implement this using code.

[@abhishekc3556]

Thank you 🔥🔥

[@saurabhN1393]

Thanks I think if(matrix[i][j] == 0) return; code is missed by Fraz in the video.

[@anixdrv]

In which language.. the solution of problem is coded?

[@aimanshaikh7201]

When beginners DSA course will start

[@BurhanAijaz]

day 20 bohut zyada late ab kal dekhunga, abhi mood nahi hai 12 k baad padne ka

[@DPCODE72]

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

[@bahanebaaz3232]

want this video because I was having doubts

[@aliaslam614]

👍💯

[@vivekgupta6696]

Maja Aggaya bhaiya

[@anupkumargorai771]

👍🏻

[@mohdumar6990]

Consistency++

[@pratyekmotivation7481]

#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

[@divyanshsagar]

Episode 20 done!

[@HarshRaj-kp7gk]

#🥰🥰

[@zeeshanansari2232]

ThnQ ones again

[@mohammedsaqib1250]

codes kab aayenge

[@rabindradocument8934]

Fraz is better than didi and bhaiya who just rant I am for you.

[@mirzaadnanbeg5987]

Reach++

[@nithins3895]

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

[@nithins3895]

Bro please help me

[@Lucifer-xt7un]

Consistency ++