Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
Summary: Flood Fill algorithm is a simple Recursive question. 1. In this problem, we need to change the old color of a cell, starting from (x,y), with the newColor given in the question. We should only colour those cells which have the old colour and not any other cell. And we should always be within the boundaries of the grid. 2. One edge case will be if newColor== oldColor. In that case, we don't need to change anything simply return the 2D image vector 3. If not we will use recursion to color all the cells having oldColor with newColor. 4. Base cases will be pretty simple. We need to stay within the boundaries of the grid and we should change only those grids who have oldColor. if (i < 0 || i>=m || j=n || image[i][j] != oldColor) return; 5. Now we need to move on 4 directions - up,down,left,right and ask recursion to color all the remaining cells having color as oldColor. Time Complexity: O(M*N) [ In worst case, we need to traverse the entire grid because all the cells might be having oldColor] Space Complexity: O(M*N) [ In worst case we start from (0,0) and pain the entire grid with newColor. This causes the recursive stack space equal to O(M*N)]
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
I have seen many videos of recursion from different channels but this series is too good and easy to understand. If possible can you share the schedule of the course. I mean to ask that after recursion which topic you are going discuss.
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
@@utkarshchauhan5827 for the first position of string do you know where it exactly lies in the matrix ? No, so we are using nested for loop to check which cell matches from there we will go ahead with the remaining characters
Episode 18 completed! 🔥🔥 Flood fill algorithm Here, the flood fill algorithm is the same algorithm used in ms paint it states that if we drop a color at a point(x, y) the whole space in the boundary will be coloured. 1) Here we will be given a grid(matrix) and a point with value indicating particular color and we have to color all the adjacent matrices which share the same color 2) Here we have check the adjacent cells ie Left, Right, Top and Bottom and also we can go beyond the boundary ie End of matrix. 3) So we have check the boundaries and adjacent matrices and shd call all recursive function for all the directions 4) We can find another edge case ie the new color is same of old color in that case we need to return Time complexity and space complexity:- 0(n*m)
Summary of flood fill algorithm. It is a recursive algorithm in which we have to change oldcolor to newcolor of cell of dimensions(x,y). Edge case :- if oldcolor== newcolor simply return the image because if we don't do so recursion will go infinitely. Base case :- there are 2 base case first it should not cross the boundaries of grid i.e( i
Notes: Problem although being somewhat straightforward, gives us an essence of how recursion can be used to solve a real world problem. The case where newColor is equal to targetColor, is something to remember as I also got a run time error in that case. The space and time complexities are T = O(M * N) (worst case we might need to repaint the entire grid) S = O(M * N) (in worst case this can be the depth of the recursion tree)
My Summarization + Code + 2 Approaches (My approach included) : So here in this question we are given a point from where we have to replace all the old color with the new color in the up, down , right , left directions So first we can access the old color as image[x][y] , then we can make a helper function / recursive function , Step 1 -> So now moving to the boundary conditions that when we have to stop so if i < 0 or j < 0 or i == n or j == m or image[i][j] not equal to the old color , then we will simply return from there Step 2 -> is to paint the current pos i.e image[i][j] Step 3 -> is to call the recursive funtion in all the 4 directions by changing the parameters i and j Time Complexity -> O(nxm) Space Complexity -> O(nxm) 1.) Code : void helper(int i, int j, int n, int m, vector &image, int oldColor, int newColor){ //base case / boundary cases if (i < 0 or j < 0 or i == n or j == m or image[i][j] != oldColor) return;
//color the current image with new color image[i][j] = newColor;
//call recursively for all the 4 directions helper(i+1, j, n, m, image, oldColor, newColor); helper(i-1, j, n, m, image, oldColor, newColor); helper(i, j+1, n, m, image, oldColor, newColor); helper(i, j-1, n, m, image, oldColor, newColor); }
vector floodFill(vector& image, int sr, int sc, int newColor) { int n = image.size(); int m = image[0].size();
int oldColor = image[sr][sc];
//if the oldColor is same as newColor , simply return the image if (oldColor == newColor) return image;
helper(sr, sc, n, m, image, oldColor, newColor);
return image; } 2.) My Approach : Done by same logic bool isValid(vector& image, int i, int j, int n, int m, int color){ if (i>=0 and i=0 and j
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
When we were sleeping u were working for us.. thnx bhaiya ♥️
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
Summary:
Flood Fill algorithm is a simple Recursive question.
1. In this problem, we need to change the old color of a cell, starting from (x,y), with the newColor given in the question.
We should only colour those cells which have the old colour and not any other cell. And we should always be within the boundaries of the grid.
2. One edge case will be if newColor== oldColor. In that case, we don't need to change anything simply return the 2D image vector
3. If not we will use recursion to color all the cells having oldColor with newColor.
4. Base cases will be pretty simple. We need to stay within the boundaries of the grid and we should change only those grids who have oldColor.
if (i < 0 || i>=m || j=n || image[i][j] != oldColor)
return;
5. Now we need to move on 4 directions - up,down,left,right and ask recursion to color all the remaining cells having color as oldColor.
Time Complexity: O(M*N) [ In worst case, we need to traverse the entire grid because all the cells might be having oldColor]
Space Complexity: O(M*N) [ In worst case we start from (0,0) and pain the entire grid with newColor. This causes the recursive stack space equal to O(M*N)]
I miss u bro😭
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
Code & explanation : 9:00
I have seen many videos of recursion from different channels but this series is too good and easy to understand.
If possible can you share the schedule of the course. I mean to ask that after recursion which topic you are going discuss.
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
@@utkarshchauhan5827 for the first position of string do you know where it exactly lies in the matrix ? No, so we are using nested for loop to check which cell matches from there we will go ahead with the remaining characters
@@utkarshchauhan5827 dry run the code you will get my point.
@@jayanthipenugonda2369 so u have clear my query with respect to word search question
your Explanation is just awesome sir💥💥
Day 18 Done ✅ consistency++
C++ & fraz++ & consistency ++🥰 love u bhaiya
wonderfully explained
Thankyou so much bhaiya for your wonderful content.
Thankyou bhaiya for this nice session
Understood bahiya 👍
How many more videos will be there bro??
Thanks for the videos. 👍👍
Excellent lecture!
Episode 18 completed! 🔥🔥
Flood fill algorithm
Here, the flood fill algorithm is the same algorithm used in ms paint it states that if we drop a color at a point(x, y) the whole space in the boundary will be coloured.
1) Here we will be given a grid(matrix) and a point with value indicating particular color and we have to color all the adjacent matrices which share the same color
2) Here we have check the adjacent cells ie Left, Right, Top and Bottom and also we can go beyond the boundary ie End of matrix.
3) So we have check the boundaries and adjacent matrices and shd call all recursive function for all the directions
4) We can find another edge case ie the new color is same of old color in that case we need to return
Time complexity and space complexity:- 0(n*m)
Summary of flood fill algorithm.
It is a recursive algorithm in which we have to change oldcolor to newcolor of cell of dimensions(x,y).
Edge case :- if oldcolor== newcolor simply return the image because if we don't do so recursion will go infinitely.
Base case :- there are 2 base case first it should not cross the boundaries of grid i.e( i
Notes:
Problem although being somewhat straightforward, gives us an essence of how recursion can be used to solve a real world problem. The case where newColor is equal to targetColor, is something to remember as I also got a run time error in that case. The space and time complexities are
T = O(M * N) (worst case we might need to repaint the entire grid)
S = O(M * N) (in worst case this can be the depth of the recursion tree)
Thanks for the lecture sir
My Summarization + Code + 2 Approaches (My approach included) :
So here in this question we are given a point from where we have to replace all the old color with the new color in the up, down , right , left directions
So first we can access the old color as image[x][y] , then we can make a helper function / recursive function ,
Step 1 -> So now moving to the boundary conditions that when we have to stop
so if i < 0 or j < 0 or i == n or j == m or image[i][j] not equal to the old color , then we will simply return from there
Step 2 -> is to paint the current pos i.e image[i][j]
Step 3 -> is to call the recursive funtion in all the 4 directions by changing the parameters i and j
Time Complexity -> O(nxm)
Space Complexity -> O(nxm)
1.) Code :
void helper(int i, int j, int n, int m, vector &image, int oldColor, int newColor){
//base case / boundary cases
if (i < 0 or j < 0 or i == n or j == m or image[i][j] != oldColor) return;
//color the current image with new color
image[i][j] = newColor;
//call recursively for all the 4 directions
helper(i+1, j, n, m, image, oldColor, newColor);
helper(i-1, j, n, m, image, oldColor, newColor);
helper(i, j+1, n, m, image, oldColor, newColor);
helper(i, j-1, n, m, image, oldColor, newColor);
}
vector floodFill(vector& image, int sr, int sc, int newColor) {
int n = image.size();
int m = image[0].size();
int oldColor = image[sr][sc];
//if the oldColor is same as newColor , simply return the image
if (oldColor == newColor) return image;
helper(sr, sc, n, m, image, oldColor, newColor);
return image;
}
2.) My Approach :
Done by same logic
bool isValid(vector& image, int i, int j, int n, int m, int color){
if (i>=0 and i=0 and j
Leetcode Problem Link :- leetcode.com/problems/flood-fill/
Done understood ❤️✅
#Fraz
Excellent Lecture bro hoping for many more❤❤❤❤❤❤❤
Consistent 🙆🏻♀️
#present
Episode 18 done!
Day 18 🔥🔥🔥
Staying consistent... Done with lecture 18.
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
🔥🔥
Please Provide C++ CODE in GITHUB REPOSITORY
Done ✌️
why we are not deleting the colour during backtracking.like we do in subset problem.kindly help i am confused
Consistency++
This question is the base of DFS
Beginner DSA series kab tak aayega bhaiya?
No HW today?
where is dp series
😊😊😊😊😊❤
Guys please tell ,time complexity m*n kaise hua,kyunki ham har grid se 4 direction me jaa rahe hai to iske bhi time complexity GP me hone chahiye jaise ke agle lecture word search waale me nikali thi,please yeh doubt clear kardo mera
Hi
you are not consistent in uploading your lectures 😂
Consistency ++