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