FastPrepVirus Spread (Intuit India)

Virus Spread (Intuit India)

Intuit logoIntuit● MediumINTERNOA
Learn

Problem statement

You are given a petri dish with a grid with some healthy cells at locations i,j. It is of dimensions N x M, where each grid point in the dish can only have the following values:

  • 0: Empty
  • 1: Has a healthy cell
  • 2: Has a virus cell

Unfortunately, a virus can make its healthy neighbors sick (infected), and you need to find the minimum time at which all the cells have the virus. A virus-cell at location [i, j] will infect healthy cells at [i-1, j], [i+1, j], [i, j-1], [i, j+1] (up, down, left and right), and this takes place in one second of time. If not all cells in the dish are infected with the virus, then return -1.

Function

minimumTimeToInfect(N: int, M: int, grid: int[][]) → int

Complete the function minimumTimeToInfect in the editor.

minimumTimeToInfect has the following parameter:

  • int N: Num of rows
  • int M: Num of columns
  • N lines of the input contains the M space-separeted elements that indicate elements in each row of the matrix

Returns int: an integer that denotes the min time for all cells to have the virus, or print -1 if not all cells in the dish are infected.

Examples

Example 1

N = 2M = 3grid = [[2, 0, 0], [1, 1, 1]]return = 3

The virus cell at (0,1) will infect the healthy cell at (0,0) after one second. After the second, the virus in (0,0) will infect the healthy cell at (1,0), and after the third second, the healthy cell in the lower right will be infected.

Example 2

N = 2M = 3grid = [[2, 0, 1], [1, 1, 0]]return = -1

The healthy cell in the top right will not be infected since it is surrounded by empty cells.

Constraints

  • 1 <= N <= 100
  • 1 <= M <= 100
  • 0 <= ar[j] <= 2

More Intuit problems

See Intuit hiring insights
public int minimumTimeToInfect(int N, int M, int[][] grid) {
    // write your code here
}
N2
M3
grid[[2, 0, 0], [1, 1, 1]]
expected3
Checking account…