You are most under rated tech content creator, it's so simply explained every single yime, keep up the great work man, hope to see more videos about DS Algo and maybe system design concepts as well.
@@techdose4u best thing about you is that you don't take hours to explain a problem, you do it within minutes and try to keep the video as short as possible exactly what most people prefer
Small refactor. You don't need to pass rows and columns of the array in the dfs function as argument because they are constants and will never change. You can use image.length and image[0].length always to evaluate row and column inside the dfs function. Does not make sense to pass them always along the recursive calls because their data will never change and remain constant
Great work bro ...u are helping a lot of programmers to understand the crux of the code,just a suggestion please make a video on using c++ stl in competitive programming.
I have not started videos on competitive programming yet. This placement season I will focus on graph, dp, heap etc. After placement materials are ready, I will start CP as well.
Sir we can do it using BFS also (similar to rotten Oranges). In DFS auxiliary stack space was O(m*n) and in BFS also space complexity is O(m*n) [for using Queue]
Bro! You are doing great job. Just a suggestion thou, jasie jo bhi question hai na, like this one is from leetcode, then do include link of the question in description as well. Anyways Keep up the good work!
I wanted to ask. Does the sequence of directions we move matter? I watched the video to understand the solution after spending hours on it. In the video the filling was done top->right->down->left . But in the code, the recursion statements were applied top, down, left, right. I am confused. Can someone clarify if the order matters here?
remembering your previous solution i submitted this class Solution { public: void color(vector< vector>& image, int sr,int sc,int source,int newcolor) { if(sr=image[0].size()) return; else if(image[sr][sc]!=source) return; image[sr][sc]=newcolor; color(image,sr-1,sc,source,newcolor); color(image,sr+1,sc,source,newcolor); color(image,sr,sc-1,source,newcolor); color(image,sr,sc+1,source,newcolor); } vector floodFill(vector& image, int sr, int sc, int newColor) { if(image[sr][sc]==newColor) return image; int source=image[sr][sc]; color(image,sr,sc,source,newColor); return image; } }; Thanks a lot for your videos.
hey awesome video. i solved this question in exactly the same way without knowing how this could be DFS. Could you please explain ? for me, it's just plain recursion being called in all directions and then the base case.
DFS is the technique where you keep traversing a single branch until there is none left, then only traverse back to do the same for every node in that branch. That is why it is called depth first search. Similarly, here we are traversing till we cannot find any adjacent colors that are the same.
No it should not give RTE... In my first attempt, I didn't check whether the source is already == new color... If already equal then simply return, no need to do dfs. If we don't check this condition then it will give RTE
yes, we can do bfs as well, size will be reduced i guess since we're not pushing the entire function call stack we're just pushing the x,y coordinates in the queue.
@@freshcontent3729 whichever you think is easy for you to understand and implement. practice both types of dfs with stack and with recursion, there may be scenarios where bfs is not possible. (some graph algos)
Hey in your playlist section in may challenge it is showing 17 videos but till now you just created 12 , some of them are showing more than once , so just checkout
I can understand that everyone needs more and more videos. But think about me as well. It is not possible to make more than one video a day. I am not working full time on TH-cam.
Awesome video Practically it's not possible to make more than one video per day with office work I agree with your comments sir Do you suggest any other resources or TH-cam channel to learn more questions like your video explanation sir?
Actually there were some videos from Gaurav sen and he used to post them. But currently he is not making regular videos. I would recommend Errichto for Competitive programming. He is awesome but I don't know if you all can understand hi accent and way of teaching. Rest all are just doing marketing on TH-cam for their gains and selling their courses. I would recommend Errichto only. He is an excellent coder.
![[안방1열 풀캠4K] 베이비몬스터 'DRIP' (BABYMONSTER FullCam)│@SBS Inkigayo 241110](http://i.ytimg.com/vi/AQ4RIghEvUs/mqdefault.jpg)
You are most under rated tech content creator, it's so simply explained every single yime, keep up the great work man, hope to see more videos about DS Algo and maybe system design concepts as well.
System design won't be possible for this season of placements. I will put it before 2021 placements.
@@techdose4u best thing about you is that you don't take hours to explain a problem, you do it within minutes and try to keep the video as short as possible exactly what most people prefer
Small refactor. You don't need to pass rows and columns of the array in the dfs function as argument because they are constants and will never change. You can use image.length and image[0].length always to evaluate row and column inside the dfs function. Does not make sense to pass them always along the recursive calls because their data will never change and remain constant
Bro i have watched all your playlist. And not a single Q which i don't understand. And that too flawlessly.. Thanks for ur help broo.
Welcome :)
Same! And everytime I see something new, I try to apply to further problems because it's always very useful
Thanks :)
I code myself after watching explanation.. God bless you 🥰
Thanks :)
Code Quality Bhaiya ka : The Best, literally,... The Best 🔥🔥🔥
TH-cam's most quality content
Thanks :)
one of the best code and explanation I ever seen , 100 time thanks bhaiya
I never understand this problem.. But after watching this video 😊 understand a lot..
😅
Excellent explanation
I like your video because precise ,easy to understand and clear explanation
Keep rocking sir🥳🥳
Thanks bro :)
Easy to understand and clean code.
Thanks for the video!
Welcome
underated channel... what a vedio:)
Thanks :)
This video was excellent, but sir the space complexity is not going to be O(1). It will be O(M*N) because of the call stack.
underrated but undefeated❤🔥❤🔥
Great work bro ...u are helping a lot of programmers to understand the crux of the code,just a suggestion please make a video on using c++ stl in competitive programming.
I have not started videos on competitive programming yet. This placement season I will focus on graph, dp, heap etc. After placement materials are ready, I will start CP as well.
Great Explanation!...like your approach for explaining the problem..thanks.
Thanks :)
Sir we can do it using BFS also (similar to rotten Oranges). In DFS auxiliary stack space was O(m*n) and in BFS also space complexity is O(m*n) [for using Queue]
Bro! You are doing great job. Just a suggestion thou, jasie jo bhi question hai na, like this one is from leetcode, then do include link of the question in description as well. Anyways Keep up the good work!
I already gave the leetcode problem number. So it should be easy to find.
Great Explanation Bro..
Java Soln using BFS:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Graphs/FloodFill.java
Thanks for sharing
Excellent explanation .....................
Thanks
Amazing video, thanks for making
Welcome :)
Good stuff
Thanks for the video!
I wanted to ask. Does the sequence of directions we move matter? I watched the video to understand the solution after spending hours on it.
In the video the filling was done top->right->down->left . But in the code, the recursion statements were applied top, down, left, right. I am confused. Can someone clarify if the order matters here?
Nice Explanation, but i did not understand the leet code problem statement even though i know DFS pattern
😅 why? The question was clearly explained with example in leetcode.
Your videos are really helpful, thanks for sharing this content
Love your explanation, thanks !!
i remember exact same kind of question and the solution last month.
i mean similar
remembering your previous solution i submitted this
class Solution {
public:
void color(vector< vector>& image, int sr,int sc,int source,int newcolor)
{
if(sr=image[0].size())
return;
else if(image[sr][sc]!=source)
return;
image[sr][sc]=newcolor;
color(image,sr-1,sc,source,newcolor);
color(image,sr+1,sc,source,newcolor);
color(image,sr,sc-1,source,newcolor);
color(image,sr,sc+1,source,newcolor);
}
vector floodFill(vector& image, int sr, int sc, int newColor) {
if(image[sr][sc]==newColor)
return image;
int source=image[sr][sc];
color(image,sr,sc,source,newColor);
return image;
}
};
Thanks a lot for your videos.
Got this for google
Yes the number of islands question from the april challenge
Nice :)
Why is the new color 3 in the 2nd example?
hey awesome video. i solved this question in exactly the same way without knowing how this could be DFS. Could you please explain ? for me, it's just plain recursion being called in all directions and then the base case.
DFS is the technique where you keep traversing a single branch until there is none left, then only traverse back to do the same for every node in that branch. That is why it is called depth first search. Similarly, here we are traversing till we cannot find any adjacent colors that are the same.
class Solution {
public:
vector floodFill(vector& image, int sr, int sc, int newColor) {
int prevVal = image[sr][sc];
image[sr][sc] = newColor;
if(prevVal == newColor) return image;
if(sc-1 >= 0 && image[sr][sc-1] == prevVal) floodFill(image,sr,sc-1,newColor);
if(sc+1 < image[0].size() && image[sr][sc+1] == prevVal) floodFill(image,sr,sc+1,newColor);
if(sr-1 >= 0 && image[sr-1][sc] == prevVal) floodFill(image,sr-1,sc,newColor);
if(sr+1 < image.size() && image[sr+1][sc] == prevVal) floodFill(image,sr+1,sc,newColor);
return image;
}
};
Have you done this in the original function itself? Looks messy 😅 It's always better to use another function for recursion.
thanks for the clear explanation
Welcome :)
this is DFS but he did not use stack here .. then how is it DFS ?
Thank you
Brother how do calculate time complexity and space complexity??
I have made some basic videos on time and space analysis. Please watch them.
Which mic do you use?
I did the same but didn't pass col and row separately and got WA, why so?
you haven't use the visited matrix in order to mark visited cells. I don't know but can you tell me that does your code gives RTE?
Exactly bro
RTE means?
No it should not give RTE...
In my first attempt, I didn't check whether the source is already == new color... If already equal then simply return, no need to do dfs.
If we don't check this condition then it will give RTE
@@techdose4u RTE : Run time error, I guess
@@techdose4u Run Time Error
Can we also solve it using BFS ?
If yes , than does the time and space complexity remains the same ?
yes, we can do bfs as well, size will be reduced i guess since we're not pushing the entire function call stack we're just pushing the x,y coordinates in the queue.
@@amitavamozumder73 in video what he did is DFS right ? but he did not use stack here .. then how is it DFS ?
@@freshcontent3729 the recursion uses the call stack of the OS, calling same function again is push, returning from a function is pop from stack.
@@amitavamozumder73 thanks, if asked this same problem in interview which one should I start with .. the BFS approach or the DFS approcach ?
@@freshcontent3729 whichever you think is easy for you to understand and implement.
practice both types of dfs with stack and with recursion, there may be scenarios where bfs is not possible. (some graph algos)
Hey in your playlist section in may challenge it is showing 17 videos but till now you just created 12 , some of them are showing more than once , so just checkout
I don't know why this is happening everytime. I will correct it. Thanks for pointing.
Thanks!
what program do you draw with?
Can we do this with BFS?
First i have codeed this but it is giving WA but taking a visited array passes.
Yes it will pass.
Can we use bfs here ?
wrong space complexity - recursion involves call stacks which are impossible to be O(1)
why can't we use bfs?
the code is similar to the minesweeper game i coded . only realised the algorithm for minesweeper is flood fill.
What’s the software you using to explain ?
his is DFS but he did not use stack here .. then how is it DFS ?
You have not made videos on GOOGLE kickstart solution as you have said promise before
Bro, he is having too much office works, that's why he is not able to make videos. There are many topics which he also wants to make but couldn't
We can simply wait for him to make videos
I can understand that everyone needs more and more videos. But think about me as well. It is not possible to make more than one video a day. I am not working full time on TH-cam.
Awesome video
Practically it's not possible to make more than one video per day with office work
I agree with your comments sir
Do you suggest any other resources or TH-cam channel to learn more questions like your video explanation sir?
Actually there were some videos from Gaurav sen and he used to post them. But currently he is not making regular videos. I would recommend Errichto for Competitive programming. He is awesome but I don't know if you all can understand hi accent and way of teaching. Rest all are just doing marketing on TH-cam for their gains and selling their courses. I would recommend Errichto only. He is an excellent coder.
I dont think the code will work for 0 1 matrix and newColor = 1 like {{0,0,0},{0,1,1}} and sr=1 sc=1
Kotlin
class Solution {
lateinit var rows: IntRange
lateinit var cols: IntRange
fun floodFill(image: Array, sr: Int, sc: Int, color: Int): Array {
if (image[sr][sc] == color) return image
rows = image.indices
cols = image.first().indices
val sourceColour = image[sr][sc]
dfs(sr, sc, sourceColour, color, image)
return image
}
fun dfs(row: Int, col: Int, sourceColor: Int, color: Int, image: Array) {
if (row in rows && col in cols && image[row][col] == sourceColor) {
image[row][col] = color
dfs(row + 1, col, sourceColor, color, image)
dfs(row - 1, col, sourceColor, color, image)
dfs(row, col + 1, sourceColor, color, image)
dfs(row, col - 1, sourceColor, color, image)
}
}
}
i love you
love you too