FastPrepResponse Time Across a City Grid

Response Time Across a City Grid

LinkedIn logoLinkedIn● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

A rectangular city grid contains blocked cells (0), locations needing a response (1), and fire stations (2). Every station begins responding at time zero. A response can move between orthogonally adjacent nonblocked cells, taking one minute per step. Stations operate simultaneously.

Return the earliest time at which every location marked 1 can be reached from some station. Return -1 if any such location cannot be reached. Return 0 when no location needs a response.

For this exercise, assume the cell codes, four-direction unit travel, passable station cells, all-locations objective and unreachable result above. They select a deterministic station-response interpretation of the reported multi-source city-grid task; they are practice conventions.

Function

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

Examples

Example 1

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

Both stations start together. Every marked location is within two steps of a station.

Example 2

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

The blocked cell separates the only location from the station.

Example 3

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

No cell is marked as needing a response.

Constraints

  • 1 <= grid.length, grid[0].length <= 100.
  • All rows have the same length and contain only 0, 1 or 2.
  • A location is reached when a response first arrives; independent stations do not block each other.

More LinkedIn problems

See LinkedIn hiring insights
public int cityResponseTime(int[][] grid) {
    // Write your code here.
}
grid[[2,1,1],[1,0,1],[1,1,2]]
expected2
Checking account…