FastPrep
Problem · Array

Minimum Time to Spread Through a Grid

Learn this problem
● MediumAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given a rectangular grid whose cells contain 0, 1, or 2. A zero is empty, a one is fresh, and a two is already active.

After each minute, every active cell makes each orthogonally adjacent fresh cell active. Return the minimum number of minutes until no fresh cell remains. Return -1 when this is impossible.

Function

minutesToSpread(grid: int[][]) → int

Examples

Example 1

grid = [[2,1,1],[1,1,0],[0,1,1]]return = 4

The wave reaches the lower-right fresh cell after four minutes.

Example 2

grid = [[2,1,1],[0,1,1],[1,0,1]]return = -1

The isolated fresh cell in the lower-left corner is unreachable.

Example 3

grid = [[0,2]]return = 0

There are no fresh cells, so no minute needs to pass.

Constraints

  • 1 <= grid.length, grid[r].length <= 200
  • Every row has the same length.
  • grid[r][c] is 0, 1, or 2.

More Amazon problems

drafts saved locally
public int minutesToSpread(int[][] grid) {
    // Write your solution here.
}
grid[[2,1,1],[1,1,0],[0,1,1]]
expected4
checking account