Find the Safest Path in a Grid
Medium · Queue & Deque · about 30 minutes
Asked at Google, Meta, Uber, Bloomberg, Microsoft.
In an n × n grid, 1 marks a thief. The safeness of a path from (0, 0) to (n-1, n-1) (4-directional moves) is the minimum Manhattan distance from any cell on the path to any thief. Return the maximum safeness over all paths.