2812. Find the Safest Path in a Grid

Array
BFS
Heap (Priority Queue)
Matrix
Binary Search

TIME

O(n^2 log n)

SPACE

O(n^2)

Intuition

Two independent pieces:

Every cell has a fixed "safeness" = its Manhattan distance to the nearest thief. A multi-source BFS starting from all thieves at once fills this in, on an open 4-neighbor grid, BFS layers coincide exactly with Manhattan distance.
A path's safeness factor is the minimum cell-safeness along it. We want the path from (0,0) to (n-1,n-1) that maximizes that minimum, a classic max-min (bottleneck) path problem.

Approach

Phase 1, distance grid (BFS):

Push all thief cells (distance 0) into a queue.
Standard BFS outward; each cell records its distance to the nearest thief.

Phase 2, max-min path (Dijkstra with a max-heap):

best[r][c] = the largest bottleneck value with which we can reach (r, c). Start at (0,0) with best = dist[0][0].
Pop the cell with the greatest bottleneck. For each neighbor, the bottleneck of extending the path is min(current_bottleneck, dist[neighbor]); if that improves best[neighbor], push it.
When (n-1, n-1) is popped, its bottleneck is the answer.

(An equivalent solution binary-searches the safeness threshold and runs a plain BFS/DFS over cells with dist >= mid; the heap approach avoids the extra log factor of repeated searches conceptually but has the same asymptotics.)

Complexity

Time: O(n² log n), BFS is O(n²); the heap phase processes O(n²) cells with heap ops
Space: O(n²), distance grid, best grid, queue/heap

Edge Cases

n = 1 → single cell; answer is its own distance (0 if it's a thief)
Start or end is a thief → distance 0 there → answer 0 (Example 1)
Whole grid reachable → answer is the max achievable bottleneck
At least one thief always exists (per constraints), so BFS always has a source

Code

from typing import List
from collections import deque
import heapq


class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        """
        2812. Find the Safest Path in a Grid
        Time: O(n^2 log n)
        Space: O(n^2)
        """
        n = len(grid)
        DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

        # Phase 1: multi-source BFS -> Manhattan distance to nearest thief.
        dist = [[-1] * n for _ in range(n)]
        q = deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    dist[r][c] = 0
                    q.append((r, c))
        while q:
            r, c = q.popleft()
            for dr, dc in DIRS:
                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: max-min (bottleneck) path via max-heap Dijkstra.
        best = [[-1] * n for _ in range(n)]
        best[0][0] = dist[0][0]
        heap = [(-dist[0][0], 0, 0)]  # negate for max-heap
        while heap:
            neg_b, r, c = heapq.heappop(heap)
            b = -neg_b
            if (r, c) == (n - 1, n - 1):
                return b
            if b < best[r][c]:
                continue
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    nb = min(b, dist[nr][nc])
                    if nb > best[nr][nc]:
                        best[nr][nc] = nb
                        heapq.heappush(heap, (-nb, nr, nc))
        return best[n - 1][n - 1]

import java.util.ArrayDeque;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 2812. Find the Safest Path in a Grid
 * Time: O(n^2 log n)
 * Space: O(n^2)
 */
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();

        // Phase 1: multi-source BFS -> Manhattan distance to nearest thief.
        int[][] dist = new int[n][n];
        for (int[] row : dist) {
            java.util.Arrays.fill(row, -1);
        }
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid.get(r).get(c) == 1) {
                    dist[r][c] = 0;
                    queue.add(new int[]{r, c});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }

        // Phase 2: max-min (bottleneck) path via max-heap Dijkstra.
        int[][] best = new int[n][n];
        for (int[] row : best) {
            java.util.Arrays.fill(row, -1);
        }
        best[0][0] = dist[0][0];
        // {bottleneck, r, c}, ordered by bottleneck descending
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        heap.add(new int[]{dist[0][0], 0, 0});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int b = top[0], r = top[1], c = top[2];
            if (r == n - 1 && c == n - 1) {
                return b;
            }
            if (b < best[r][c]) {
                continue;
            }
            for (int[] d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    int nb = Math.min(b, dist[nr][nc]);
                    if (nb > best[nr][nc]) {
                        best[nr][nc] = nb;
                        heap.add(new int[]{nb, nr, nc});
                    }
                }
            }
        }
        return best[n - 1][n - 1];
    }
}