Posted on May 9, 2020

Understanding how Kami-2 works with flood fill algorithm. Google Interview question.

#computerscience #webdev #career #tutorial

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[0]+dx; let y = dir[1]+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[0].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; };

Breadth-First Traversal:

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[0]; let dy = node[1]; image[dx][dy] = newColor; for(let dir of dirs){ let x = dx+dir[0]; let y = dy+dir[1]; if(x<0 || y<0 || x>=image.length || y>=image[0].length || image[x][y] != oldColor) continue; queue.push([x,y]); } } } return image; };