Amazon interview question: Implement FloodFill algorithm

Interview question:
Given a image in the form of 2D matrix fill color for a section in the image using bucket coloring strategy.
or
Implement Flood fill Algorithm
Flood fill algorithm helps in visiting each and every point in a given area. It determines the area connected to a given cell in a multi-dimensional array.
Applications: Bucket Fill in Paint, Solving a Maze and many more
Python Code:
github.com/Narengowda/TechDum...
Java code:
gist.github.com/VarunVats9/14...

[@user-ec6kt2fg7m]

It is always an Indian helping me with stuff like this. You guys rock!

[@mikhailmikheev8043]

That's a very nice explanation :) Thank you and keep it up!

[@tirthdoshi7463]

Thanks ! Was great to understand this clearly!

[@richardchen7097]

i like the music in the background

[@ahmetavc8868]

there is no need to keep auxiliary array for visited positions since we turn visited 2's to 3.

[@vinayreddykallu8131]

if we dont want to chage the value,then u need the array because it may run into infinite loop

[@viktoralferov2874]

@@vinayreddykallu8131 Hi. Or add a bitmap index (for visited grid cells maped to array of bit)

[@shantanukshire79]

@@vinayreddykallu8131 True, this will occur when newColor and oldColor are same. However we can just initially handle this case by checking replace point color and directly return if its the same.

[@TheRaviraaja]

Corner case - if you want to fill color 1 with 1 then you cannot determined end - infinite loop push and pop happen - stack overflow.

[@mohammedabdulbari3460]

Since it is a stack based approach and only the valid neighbors are added (if it is same as the clicked color), do we need a visited array? since we can just validate if popped index is equal to newcolor, move on and pop again till empty. would this be inefficient in anyway?

[@AshishRawat-zl6te]

I was abt to put the same comment, we don't need to have a visited array. Apart from this, really great explanation!

[@rplusgdj]

Thanks Naren. I've one question, is there any specific advantage for using stack in this context? I feel, queue can give cleaner solution with same complexity. And, before adding to queue or stack, we should check if that node is in visited map.

[@NavneetVermalivefree]

I think we can solve this problem using connected components which will actually reduce the whole complexity if the problem. The time for coloring will be less than log(n). I don't know why we have used the BFS/DFS over here.

[@josephluce9886]

*facepalm*

[@xxRAP13Rxx]

@@josephluce9886 What is the face palm for?

[@RajeevKumar-xz2zr]

Visited array should be used while pushing the value into the stack there is no point pushing same value in the stack twice. It Unnecessarily increases some processing time.

[@AnmolSingh-dz6tj]

I'm getting an error of list index is out of range on ""img[r][c]!=color:"
Any suggestions why?
(doing in python3)

[@DanielNetSet]

5:50 how do you avoid adding the same value in the stack? seems to me that there would be duplicates (3,1)
same with 7:40, when you seem to reach the end of the current neighbors when you add (2,3) to the stack at 7:30?

[@iQwert789]

Why is DFS needed here ? it can be solved with simple recursion going top, right, bottom, left and exit condition is when color doesn’t match

[@amaljose8742]

Thanks, what is the difference when top, left, right, bottom neibhours are only selected

[@eksortso]

In that case, if you want to flood fill (e.g.) a checkerboard pattern, then each cell would be considered a separate segment. If diagonal neighbors are included though, then all cells with the same color in the checkerboard would constitute a single region. Very different results.

[@nnvskh8269]

do see the same thing in that 2D array?

[@satenderking]

can we use this algo for the figures with no previous color??? how??

[@alexanderhess7742]

You don't need previous color, but you do need a ROI, obviously. How else do you define what is a "region"?

[@AshwaniKumar-uo3ci]

Using BFS queue
We only add the neighbours which have the required color to be updated.
And to avoid the duplication of neighbours instead of using visited we can simply updated the color before inserting the neighbour into the queue.
The use of visited array should be avoided because that is achievable by checking the value in the cell.
Below is working code
void floodFillMatrix(int mat[][4], int row, int col, int i, int j, int newColor) {
int oldColor = mat[i][j];
queue q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair current = q.front();
q.pop();
mat[current.first][current.second] = newColor;
pair neigh[] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
for (int i = 0; i < sizeof(neigh) / sizeof(neigh[0]); i++) {
int x = neigh[i].first + current.first;
int y = neigh[i].second + current.second;
if (x >= 0 && x < row && y >= 0 && y < col && mat[x][y] == oldColor) {
mat[x][y] = newColor;
q.push(make_pair(x, y));
}
}
}
}
void printMatrix(int mat[][4], int row, int col) {
for (int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
cout

[@akshaytelang4532]

its a leetcode 733 question

[@yldrmcs]

a computational hydrologist here, with all due respect, this is not even close to the algorithm in which we refer to "FloodFill" algorithm :)

[@AshwaniKumar-uo3ci]

Yes BFS should be used not DFS since water reaches same distance everwhere at a given time