Understanding how Kami-2 works with flood fill algorithm. Google Interview question.
Tags: computerscience, webdev, career, tutorial
Published: 2020-05-09 15:25:09

If you haven't played Kami-2, I would urge you to check it out on the <a href="https://play.google.com/store/apps/details?id=com.stateofplaygames.kami2&hl=en_IN">Play store</a> or <a href="https://apps.apple.com/us/app/kami-2/id1133161444">App store</a>. 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 : 

<img src="https://media.giphy.com/media/f6nEWwJf1iFomVEpJU/giphy.gif" />

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 <strong>"FAANG"</strong> interviews

For the sake of better understanding consider this image grid : 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/619eu5l0e6naookapi3i.jpg)

And we want to convert all red's to blue. 

Step 1 : Choose one red cell and look around the adjacent neighboring cells.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/059xdt2x9157k18r6j6y.jpg)

We basically see all 4 directions, North, South, East, West. 

Converting that to code : 

```javascript

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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/tjyqvv9mhlw0wmepejnx.jpg)

```javascript
   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: 

<img src="https://upload.wikimedia.org/wikipedia/commons/5/5e/Wfm_floodfill_animation_stack.gif" />

```javascript
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: 

<img src = "https://upload.wikimedia.org/wikipedia/commons/b/b6/Wfm_floodfill_animation_queue.gif" />

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

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

Happy coding! :) 


github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/FloodFill.js