## DEV Community 👩‍💻👨‍💻 # Understanding how Kami-2 works with flood fill algorithm. Google Interview question.

If you haven't played Kami-2, I would urge you to check it out on the Play store or App store. It's a beautifully designed puzzle in which the main goal is to convert all the tiles on the board to a single color in as few moves as possible.

A short gif on the same : The basic working can be boiled down to 2 main functions.
1> Look around the adjacent neighbor cells.
2> If they're the same color as current cell, change their color and repeat.

This is a question asked at all the "FAANG" interviews

For the sake of better understanding consider this image grid : And we want to convert all red's to blue.

Step 1 : Choose one red cell and look around the adjacent neighboring cells. We basically see all 4 directions, North, South, East, West.

Converting that to code :

``````
let dirs = [[-1,0],[0,1],[0,1],[-1,0]];
let arr = []; // for storing the cells
let dx = 2;
let dy = 2;
for(int dir:dirs){
let x = dir+dx;
let y = dir+dy;
if(cell[x][y] == 'red'){
arr.push([x,y]);
}
}
``````

Step 2: Convert all the red cells to blue cells and repeat step 1 on the converted cells.

``````   cell[x][y] = 'blue'
``````

Here, we have two options to go with, Depth First Traversal and Breadth-First Traversal. Time Complexity for both will be O(mn) on average.

Let's implement both.

Depth First Traversal:

``````var dfs = function(image,sr,sc,newColor,oldColor){
if(sr<0 || sc<0 || sr>=image.length || sc>=image.length || image[sr][sc] != oldColor)
return;
image[sr][sc] = newColor;
dfs(image,sr-1,sc,newColor,oldColor);
dfs(image,sr,sc+1,newColor,oldColor);
dfs(image,sr+1,sc,newColor,oldColor);
dfs(image,sr,sc-1,newColor,oldColor);
}

var floodFill = function(image, sr, sc, newColor) {
let oldColor = image[sr][sc];
if(oldColor == newColor) return image;
dfs(image,sr,sc,newColor,oldColor);
return image;
};
``````

``````var floodFill = function(image, sr, sc, newColor) {
let oldColor = image[sr][sc];
if(oldColor == newColor) return image;
let queue = [];
queue.push([sr,sc]);
let dirs = [[-1,0],[0,1],[1,0],[0,-1]];
while(queue.length>0){
let size = queue.length;
for(let i=0;i<size;i++){
let node = queue.shift();
let dx = node;
let dy = node;
image[dx][dy] = newColor;
for(let dir of dirs){
let x = dx+dir;
let y = dy+dir;
if(x<0 || y<0 || x>=image.length || y>=image.length || image[x][y] != oldColor) continue;
queue.push([x,y]);
}
}

}
return image;
};
``````

I hope you understood the flood fill algorithm and liked my explanation.

Happy coding! :) 