Flood Fill | Leetcode
Vložit
- čas přidán 10. 05. 2020
- This video explains a very important interview question based on depth first search,i.e., recursion and backtracking. The problem name is flood fill. This is a very good problem to learn and practice DFS and recursion. I have explained the problem with intuition for solving. I have shown the solution with proper example and have also explained the CODE at the end of the video. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
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
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 :)
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
I code myself after watching explanation.. God bless you 🥰
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..
😅
Your videos are really helpful, thanks for sharing this content
Easy to understand and clean code.
Thanks for the video!
Welcome
Code Quality Bhaiya ka : The Best, literally,... The Best 🔥🔥🔥
I did the same but didn't pass col and row separately and got WA, why so?
Excellent explanation
I like your video because precise ,easy to understand and clear explanation
Keep rocking sir🥳🥳
Thanks bro :)
Love your explanation, thanks !!
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 :)
underrated but undefeated❤🔥❤🔥
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]
Great Explanation Bro..
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?
CZcams's most quality content
Thanks :)
underated channel... what a vedio:)
Thanks :)
Thanks for the video!
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.
Thank you
Thanks!
Why is the new color 3 in the 2nd example?
Good stuff
what program do you draw with?
Amazing video, thanks for making
Welcome :)
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.
Java Soln using BFS:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Graphs/FloodFill.java
Thanks for sharing
Which mic do you use?
Can we do this with BFS?
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.
Excellent explanation .....................
Thanks
Can we use bfs here ?
Brother how do calculate time complexity and space complexity??
I have made some basic videos on time and space analysis. Please watch them.
thanks for the clear explanation
Welcome :)
this is DFS but he did not use stack here .. then how is it DFS ?
First i have codeed this but it is giving WA but taking a visited array passes.
Yes it will pass.
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 :)
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.
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
why can't we use bfs?
What’s the software you using to explain ?
his is DFS but he did not use stack here .. then how is it DFS ?
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)
the code is similar to the minesweeper game i coded . only realised the algorithm for minesweeper is flood fill.
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.
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
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.
wrong space complexity - recursion involves call stacks which are impossible to be O(1)
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 CZcams.
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 CZcams 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 CZcams for their gains and selling their courses. I would recommend Errichto only. He is an excellent coder.
i love you
love you too
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)
}
}
}