How should I practice Find the Safest Path in a Grid?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen and onsite interview problems in FastPrep.

Is Find the Safest Path in a Grid associated with Google?

FastPrep tags this as a Google phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Find the Safest Path in a Grid

Google● MediumINTERNNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given an n x n binary matrix grid. A cell containing 1 contains a thief, and a cell containing 0 is empty. You start at (0, 0) and want to reach (n - 1, n - 1).

In one move, you may travel up, down, left, or right to a cell inside the grid. You may enter a cell containing a thief.

The safeness factor of a path is the minimum Manhattan distance between any cell on that path and any thief in the grid. Return the maximum safeness factor among all paths from the start to the destination.

The Manhattan distance between cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

Function

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

Examples

Example 1

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

The start and destination both contain thieves, so every valid path has safeness factor 0.

Example 2

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

A path along the left and bottom edges always stays at least Manhattan distance 2 from the thief at (0, 2), and no path can do better.

Example 3

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

There is a route whose closest approach to either thief is distance 2; every start-to-destination route has a cell no farther than 2 from a thief.

Constraints

1 <= n == grid.length <= 400.
grid[i].length == n.
grid[i][j] is either 0 or 1.
The grid contains at least one thief.