Covid Matrix, Implementing Breadth-First Search Algorithm with virus.

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 infected1 or healthy 0, 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 :

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.

Brute Force:

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.

Undestanding efficient way

1> Directions

Infection can spread in four directions :

so our direction array can be written as :

let dirs = [[1,0],[0,-1],[0,1],[-1,0]];

2> Storing infected human and its neighbouring humans which will be infected next day

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

Let's call it

Quarantine Data Structure

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.

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

Queue

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..

Implement queue :

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:

Let's put this all together:

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:

[[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