Covid Matrix, Implementing Breadth-First Search Algorithm with virus. 
Tags: javascript, algorithms, interview, career
Published: 2020-04-13 16:02:19

You're in the middle of an outbreak, the government needs your help in determining how many days will it take for the entire population to be infected. 

You're given a 2D matrix, each cell is either infected<strong>1</strong> or healthy <strong>0</strong>, an Infected human can infect adjacent human ie top, down, left, right healthy cells every day. Determine how many days will it take for the infection to infect all humans.

Eg: consider the matrix : 
```javascript
Input: 
[[0, 1, 1, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0]]

After day 1 : 
[[1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 1, 0, 1, 1],
 [1, 1, 1, 0, 1]]

After day 2 :
[[1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1]]

So it takes 2hrs for infection to infect all humans.
```

<h3>Brute Force: </h3>

Brute Force approach would be to loop through the array, for each element check is any of the neighboring cells is an infected human, if it is then the human will be infected.

This method might work for inputs where the number of infected humans is much bigger than the number of healthy humans, but for a sparse array where the number of infection << number of humans, this approach might not work well.

<h3> Undestanding efficient way</h3>

<h5> 1> Directions </h5> 
Infection can spread in four directions : 

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

so our direction array can be written as : 

```javascript
let dirs = [[1,0],[0,-1],[0,1],[-1,0]];
```
<h5> 2> Storing infected human and its neighbouring humans which will be infected next day </h5>

For each day we need some sort of Data Structure which will store all infected humans:

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

Let's call it <h5>Quarantine Data Structure</h5>.

Operations on the Quarantine Data Structure will be in the following order:

1> Store all infected humans in the data structure.
2> Iterate over the infected humans since it's neighboring humans are infected, store them in the data structure.
3> repeat the same for each day.

So we're essentially 
1> pushing all infected humans on to data structure
2> for a day x, we go through x infected humans. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/0lhphjsbaknwj5l5kkg9.png)

A queue will work the best with this, to understand why? Imagine this:

<h5> Queue </h5>

Day 0> Add push all infected humans to queue.

Day 1> Pop an infected human from the queue, his neighbors will be infected, so push them into the queue, but consider only the infected humans from day 1, if iterate through the entire queue, everyone would be infected on Day 1.

Day 2> Now repeat the same for Day 2. and so on..

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/82ijbr81jfm3qtgd01wo.png)


Implement queue : 
```javascript
let queue = [];
// since in javascript, the array provides push and shift operations,
// there's no need to implement queue. 
// for java use Queue<Integer> queue = new LinkedList<>();
```

Now let's simulate it: 

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

Let's put this all together:
```javascript
var minDay = function(grid){
  let queue = [];
  let target = grid.length * grid[0].length;
  let count = 0;
  let days = 0;
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      if(grid[i][j] == 1){
        queue.push([i,j]);                 //populate queue for day 0
        count++;
      }
    }
  }

  let dirs = [[-1,0],[0,-1],[1,0],[0,1]];
  while(queue.length>0){
    let size = queue.length; 
    if(count == target) return days;              //everyone is infected
    
    //now iterate queue only for that day
    for(let i=0;i<size;i++){
      let curr = queue.shift();
      for(let dir of dirs){
        let x = curr[0] + dir[0];
        let y = curr[1] + dir[1];
        if(x >= 0 && x<grid.length          //check if the cordinates are valid  
           && y>=0 && y<grid[0].length 
           && grid[x][y] == 0){             // check if the grid[x][y] is human 
          count++;
          queue.push([x,y]);
          grid[x][y] = 1;
        }
      }
    }
    days++;
  }
  return -1;
}
```

Congratulations you've just implemented Breadth First Search Algorithm. 

In Breadth First Search Traversal, the nodes explore its neighbours level by level. In our case the level is the number of days, and the total number of days,s it takes to infect the grid is the number of the height of the graph.

It was easy right? 

As a challenge, consider the case where people take precautions maintain social distancing, wash hands properly etc. Consider such entries as 2, as an example: 

```javascript

[[2, 1, 1, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 0, 2, 1],
 [0, 1, 0, 2, 2]]

0: healthy humans
1: infected humans
2: humans who are practicing healthy habits
```


github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ZombieMatrix.js