Napman's Notes

Find the Safest Path in a Grid

Properties1
tagsreview/leetcode

3 min read

2812. Find the Safest Path in a Grid

Difficulty: Medium | Date: 2026-06-30

Patterns: BFS | Binary Search | Graphs Data Structures: Matrix

Problem

Given an n x n grid where cells are either 0 (empty) or 1 (thief), find the path from (0,0) to (n-1, n-1) that maximizes the “safety factor” - defined as the minimum Manhattan distance from any thief along the path. Return that maximum safety factor.

My Approach

I knew it was a BFS problem with a twist but couldn’t piece it together on my own. After seeing the hints, it clicked: two-phase approach. First, do a multi-source BFS starting from all thief cells simultaneously to compute the safety factor (min distance to any thief) for every cell in the grid. Second, binary search on the answer - the candidate safety value - and for each candidate, do a BFS from start to end using only cells with safety >= candidate to check feasibility.

The binary search bounds are 0 (minimum possible) and ROWS + COLS (maximum possible Manhattan distance in the grid).

Key Insight

The problem decomposes into two separate BFS passes. The first is a global multi-source BFS from all thieves at once to precompute safety factors - this is the same pattern as “distance to nearest 0” problems. The second uses binary search on the answer with a BFS feasibility check, which sidesteps needing to think about Dijkstra or other shortest-path variants.

Solution

from collections import deque
 
def maximumSafenessFactor(grid):
    ROWS, COLS = len(grid), len(grid[0])
    DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
 
    # Phase 1: multi-source BFS from all thieves to compute safety factors
    safety = [[0] * COLS for _ in range(ROWS)]
    q = deque()
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                q.append((r, c, 0))
                safety[r][c] = 0
            else:
                safety[r][c] = -1  # unvisited
 
    while q:
        r, c, dist = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS and safety[nr][nc] == -1:
                safety[nr][nc] = dist + 1
                q.append((nr, nc, dist + 1))
 
    # Phase 2: binary search on the minimum safety threshold
    def canReach(min_safe):
        if safety[0][0] < min_safe or safety[ROWS-1][COLS-1] < min_safe:
            return False
        visited = [[False] * COLS for _ in range(ROWS)]
        q = deque([(0, 0)])
        visited[0][0] = True
        while q:
            r, c = q.popleft()
            if r == ROWS - 1 and c == COLS - 1:
                return True
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and not visited[nr][nc] and safety[nr][nc] >= min_safe:
                    visited[nr][nc] = True
                    q.append((nr, nc))
        return False
 
    lo, hi = 0, ROWS + COLS
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if canReach(mid):
            lo = mid
        else:
            hi = mid - 1
 
    return lo

Complexity

  • Time: O(n^2 log n) - O(n^2) for multi-source BFS, O(n^2 log n) for binary search with BFS each iteration
  • Space: O(n^2) - safety factor grid and visited arrays

Prerequisites

Graph View

Backlinks