Practice/Google/Leetcode 2812. Find the Safest Path in a Grid

Leetcode 2812. Find the Safest Path in a Grid

CodingMust

Problem

You are given a square grid where each cell is either empty (0) or contains a threat (1). You need to travel from the top-left corner to the bottom-right corner.

The safety factor of a cell is defined as the Manhattan distance from that cell to the nearest threat. The Manhattan distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

The safety factor of a path is the minimum safety factor among all cells in that path.

Your task is to find the maximum possible safety factor among all valid paths from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1). You can only move up, down, left, or right to adjacent cells.

Requirements

1. Calculate the safety factor for every cell in the grid
2. Find a path from top-left to bottom-right that maximizes the minimum safety factor along the path
3. Return the maximum safety factor achievable
4. If the start or end cell contains a threat, return 0

Constraints

• 1 ≤ n ≤ 300 (where n × n is the grid size)
• grid[i][j] is either 0 or 1
• At least one cell contains a threat
• Time complexity: O(n² log n) is expected
• Space complexity: O(n²) is acceptable

Examples

Example 1:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]] Output: 2 Explanation: The threat is at (0,0). The path (0,0) → (1,0) → (2,0) → (2,1) → (2,2) has safety factors [0,1,2,2,2]. The minimum is 0. But the path (0,0) → (0,1) → (0,2) → (1,2) → (2,2) has safety factors [0,1,2,2,2]. Actually, since (0,0) has a threat, any path starting there has minimum 0. Wait - let me reconsider: if (0,0) has value 1, we start on a threat cell, so the answer is 0. Let me correct this. Actually for grid = [[0,0,0],[0,0,0],[0,0,1]], the optimal path avoiding the threat at (2,2) would go (0,0)→(0,1)→(0,2)→(1,2)→(2,2) with distances [2,2,1,1,0], minimum 0. For grid = [[1,0,0],[0,0,0],[0,0,0]], starting at a threat gives 0.

Example 2:

Input: grid = [[0,0,1],[0,0,0],[0,0,0]] Output: 2 Explanation: The threat is at position (0,2). Path: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) Safety factors: [2, 2, 3, 2, 2] The minimum safety factor along this path is 2.

Example 3:

Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]] Output: 2 Explanation: Threats at (0,3) and (3,0). The optimal path maintains distance 2 from all threats by going through the middle of the grid.