Flood Fill | Leetcode

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

[@rohitsrivastava5414]

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]

System design won't be possible for this season of placements. I will put it before 2021 placements.

[@aniketpandey1913]

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

[@rahulchaubey8988]

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.

[@techdose4u]

Welcome :)

[@hortsss]

Same! And everytime I see something new, I try to apply to further problems because it's always very useful

[@techdose4u]

Thanks :)

[@willturner3440]

I code myself after watching explanation.. God bless you 🥰

[@techdose4u]

Thanks :)

[@Alikhan1993]

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

[@Brijeshkumar-lk5mt]

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.

[@vishwassahu]

KZbin's most quality content

[@techdose4u]

Thanks :)

[@md_aaqil8027]

Excellent explanation I like your video because precise ,easy to understand and clear explanation Keep rocking sir🥳🥳

[@techdose4u]

Thanks bro :)

[@asitkumar3164]

Code Quality Bhaiya ka : The Best, literally,... The Best 🔥🔥🔥

[@vijayabiradar687]

Easy to understand and clean code. Thanks for the video!

[@techdose4u]

Welcome

[@dhir_tech]

one of the best code and explanation I ever seen , 100 time thanks bhaiya

[@meghamalviya8495]

Great Explanation!...like your approach for explaining the problem..thanks.

[@techdose4u]

Thanks :)

[@jainanish94]

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!

[@techdose4u]

I already gave the leetcode problem number. So it should be easy to find.

[@ethanhunt3671]

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]

[@yashpaunikar671]

underrated but undefeated❤‍🔥❤‍🔥

[@kunalsoni7681]

I never understand this problem.. But after watching this video 😊 understand a lot..

[@techdose4u]

😅

[@binitkumarsingh8296]

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.

[@techdose4u]

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.

[@suhanshupatel9204]

underated channel... what a vedio:)

[@techdose4u]

Thanks :)

[@MonirsOfficial]

Great Explanation Bro..

[@arthamsreenivas8858]

Nice Explanation, but i did not understand the leet code problem statement even though i know DFS pattern

[@techdose4u]

😅 why? The question was clearly explained with example in leetcode.

[@rajeshseptember09]

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.

[@FaisalSaifi]

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.

[@dhanashreegodase4445]

Excellent explanation .....................

[@techdose4u]

Thanks

[@TheMcallist1]

Amazing video, thanks for making

[@techdose4u]

Welcome :)

[@sundaypodcom]

Good stuff

[@elvissam1401]

Your videos are really helpful, thanks for sharing this content

[@shreelakshmi6890]

thanks for the clear explanation

[@techdose4u]

Welcome :)

[@freshcontent3729]

this is DFS but he did not use stack here .. then how is it DFS ?

[@amruthaj4262]

Why is the new color 3 in the 2nd example?

[@NikhilKumar-oy7mx]

i remember exact same kind of question and the solution last month.

[@NikhilKumar-oy7mx]

i mean similar

[@NikhilKumar-oy7mx]

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.

[@pujaridevanjagadeesan2170]

Got this for google

[@agileprogramming7463]

Yes the number of islands question from the april challenge

[@techdose4u]

Nice :)

[@anirudhv0062]

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?

[@nobita7231]

Brother how do calculate time complexity and space complexity??

[@techdose4u]

I have made some basic videos on time and space analysis. Please watch them.

[@amotekundev]

Thank you

[@nishantshah_]

Love your explanation, thanks !!

[@surajmaity6194]

Thanks for the video!

[@jaydeepmahajan6598]

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

[@techdose4u]

I don't know why this is happening everytime. I will correct it. Thanks for pointing.

[@dipeshdarji6253]

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?

[@safalyaghoshroy2405]

Exactly bro

[@techdose4u]

RTE means?

[@spetsnaz_2]

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

[@sarbojitsarkar1226]

@@techdose4u RTE : Run time error, I guess

[@dipeshdarji6253]

@@techdose4u Run Time Error

[@andrewchen861]

Thanks!

[@safalyaghoshroy2405]

First i have codeed this but it is giving WA but taking a visited array passes.

[@techdose4u]

Yes it will pass.

[@awakashsinha9926]

I did the same but didn't pass col and row separately and got WA, why so?

[@jazlynlin9995]

wrong space complexity - recursion involves call stacks which are impossible to be O(1)

[@chandrakantgarg1069]

Can we also solve it using BFS ? If yes , than does the time and space complexity remains the same ?

[@amitavamozumder73]

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]

@@amitavamozumder73 in video what he did is DFS right ? but he did not use stack here .. then how is it DFS ?

[@amitavamozumder73]

@@freshcontent3729 the recursion uses the call stack of the OS, calling same function again is push, returning from a function is pop from stack.

[@freshcontent3729]

@@amitavamozumder73 thanks, if asked this same problem in interview which one should I start with .. the BFS approach or the DFS approcach ?

[@amitavamozumder73]

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

[@victorvondoom2350]

the code is similar to the minesweeper game i coded . only realised the algorithm for minesweeper is flood fill.

[@akhilnarayanan7182]

Which mic do you use?

[@rajeshbammidy180]

Java Soln using BFS:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Graphs/FloodFill.java

[@techdose4u]

Thanks for sharing

[@Meethu69]

why can't we use bfs?

[@saunaknandi1814]

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

[@programmingstuff5741]

You have not made videos on GOOGLE kickstart solution as you have said promise before

[@spetsnaz_2]

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

[@spetsnaz_2]

We can simply wait for him to make videos

[@techdose4u]

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

[@md_aaqil8027]

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 KZbin channel to learn more questions like your video explanation sir?

[@techdose4u]

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 KZbin for their gains and selling their courses. I would recommend Errichto only. He is an excellent coder.

[@_abhishekmj_]

Can we do this with BFS?

[@ИкромХасанбаев]

what program do you draw with?

[@amittiwari360]

Can we use bfs here ?

[@fatimajaffal9843]

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; } };

[@techdose4u]

Have you done this in the original function itself? Looks messy 😅 It's always better to use another function for recursion.

[@pratiksarvan]

What’s the software you using to explain ?

[@freshcontent3729]

his is DFS but he did not use stack here .. then how is it DFS ?

[@boomer_mcghee]

i love you

[@techdose4u]

love you too

[@CostaKazistov]

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) } } }