NeetCode #632LC-2812MediumAdvanced Graphs
← Back to All Problems#632 · #2812 · Find the Safest Path in a Grid(找出最安全路径)
📌 Problem Statement & Constraints
You are given an
n x n grid where 1 is a thief and 0 is empty. The safeness factor of a path is the minimum Manhattan distance from any cell on the path to the nearest thief. Return the maximum safeness factor over all paths from the top-left to the bottom-right. Constraints: 1 <= n <= 400.💡 Core Algorithmic Approaches
- Step 1: multi-source BFS from every thief computes each cell's distance to the nearest thief.
- Step 2: run a max-heap Dijkstra where the key is the minimum distance along the path.
- This is the same "maximise the bottleneck" template as Path With Minimum Effort.
- The two-phase structure separates the distance computation from the path search.
💻 Benchmark Python3 Implementation
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
from collections import deque
import heapq
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return 0 # start or end occupied by a thief
# phase 1: distance to the nearest thief (multi-source BFS)
dist = [[-1] * n for _ in range(n)]
q = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
dist[i][j] = 0
q.append((i, j))
while q:
r, c = q.popleft()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
# phase 2: maximise the minimum safeness along the path
h = [(-dist[0][0], 0, 0)]
seen = {(0, 0)}
while h:
neg, r, c = heapq.heappop(h)
cur = -neg
if r == n - 1 and c == n - 1:
return cur
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
heapq.heappush(h, (-min(cur, dist[nr][nc]), nr, nc))
return 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log n): the BFS is linear and the Dijkstra pushes each cell once.
💾 Space Complexity
O(n^2) for the distance grid and the heap.
⚠️ Interview Pitfalls & Follow-ups
- Computing the distance per path: O(paths * n^2); the precomputed grid makes it O(1) per cell.
- Using a min-heap for the path search: the bottleneck must be maximised.
- Summing the safeness values: the path's safeness is its minimum.
- Forgetting the start/end thief check: a thief on the start or end makes the answer 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.