FastPrepRat's Safest Path

Rat's Safest Path

Google logoGoogle● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

In a square grid, 1 is open land and 0 is blocked water. Move from source to target through open cells in four directions. A stationary cat occupies cat.

The safety of a path is the minimum Manhattan distance from the cat among all cells on the path. Return the maximum possible safety, or -1 when no path exists.

Function

maximumPathSafety(grid: int[][], source: int[], target: int[], cat: int[]) → int

Examples

Example 1

grid = [[1,1,1],[1,0,1],[1,1,1]]source = [0,0]target = [2,2]cat = [0,2]return = 2

The route around the left and bottom edges stays at least two cells from the cat.

Example 2

grid = [[1,1,1],[1,1,1],[1,1,1]]source = [0,0]target = [2,0]cat = [0,2]return = 2

The left column keeps distance at least two.

Constraints

  • 1 <= grid.length == grid[i].length <= 300.
  • Coordinates are valid; source and target may be blocked.

Source note: Author-written prompt excerpt retained for source fidelity.

More Google problems

See Google hiring insights
public int maximumPathSafety(int[][] grid, int[] source, int[] target, int[] cat) {
    // Write your code here.
}
grid[[1,1,1],[1,0,1],[1,1,1]]
source[0,0]
target[2,2]
cat[0,2]
expected2
Checking account…