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 Amazon phone screen and onsite interview problems in FastPrep.

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

FastPrep tags this as a Amazon 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

Amazon● HardFULLTIMEPHONE SCREENONSITE INTERVIEW

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.

Start at (0, 0) and move to (n - 1, n - 1). Each move goes one cell up, down, left, or right, and a path may pass through a thief cell.

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

The Manhattan distance between (r, c) and (x, y) is |r - x| + |c - y|.

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 path has safeness factor 0.

Example 2

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

A path through the left and bottom area 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

A route through the central corridor remains at least distance 2 from both corner thieves.

Constraints

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