15% off all plans & roadmaps Use code
See plans
Editorial
Core insight
Find the Safest Path in a Grid · Graph Traversal Patterns (DFS & BFS)
Core Insight for Find the Safest Path in a Grid
The solution requires two distinct phases, both relying on graph traversal principles.
Phase 1: Efficient Distance Calculation (Multi-Source BFS) The brute force method calculates distances in . However, we can calculate the distance from every cell to its nearest thief in using Multi-Source Breadth-First Search. Instead of starting a BFS from one node, we initialize the queue with all thief coordinates simultaneously. The BFS expands layer by layer; the first time a cell is visited, it is guaranteed to be reached via the shortest path from the closest thief. This creates a "distance field" grid.
Phase 2: Maximizing the Minimum Value (Modified Dijkstra) Once we have the distance grid, the problem becomes finding a path from start to end such that the minimum value observed on the path is maximized. This is a variation of the Shortest Path problem. In standard Dijkstra, we greedily pick the path with the smallest total cost. Here, we greedily pick the path with the highest bottleneck capacity.
We use a Priority Queue (Max-Heap) to store states (safeness, r, c). The safeness value represents the minimum distance encountered so far on the path from the start to (r, c). By always expanding the node with the highest current safeness, we ensure that when we reach the target, we have found the optimal path.
Visual Description: Imagine the distance grid as a terrain map where high distance values represent peaks and low values (near thieves) represent valleys. You are trying to drive from the top-left to the bottom-right while staying at the highest possible elevation. You start at your current elevation. At every step, you look at all reachable neighbors and move to the one that forces you to descend the least. A Max-Heap allows you to essentially "flood" the terrain from the highest accessible points downwards until you reach the destination.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 2812: Find the Safest Path in a Grid Solution & Explanation
Problem Overview
TL;DR: The optimal solution first computes the distance from every cell to the nearest thief using Multi-Source BFS, then uses a modified Dijkstra's Algorithm (Best-First Search) to find a path that maximizes the minimum distance encountered.
In LeetCode 2812: Find the Safest Path in a Grid, you are provided with an grid containing empty cells (0) and thieves (1). Your objective is to navigate from the top-left corner to the bottom-right corner . The quality of a path is determined by its "safeness factor," defined as the minimum Manhattan distance between any cell on that path and any thief in the grid. You must return the maximum possible safeness factor achievable.
This problem combines distance field calculation with a "bottleneck path" problem, making it a classic candidate for graph traversal optimizations.
Brute Force Approach for Find the Safest Path in a Grid
A naive brute force approach attempts to evaluate every possible path from the start to the end to find the one with the highest safeness factor.
- Calculate Distances: Iterate through every cell in the grid. For each cell, iterate through every thief to find the minimum Manhattan distance.
- Find Paths: Use Depth First Search (DFS) to explore all simple paths from to .
- Evaluate: For each path found, determine the minimum distance value among all cells in that path. Track the maximum of these minimums.
1# Pseudo-code for Naive Approach
2def brute_force(grid):
3 # 1. Calculate distances O(N^4)
4 dist_matrix = calculate_all_distances_naive(grid)
5
6 max_safeness = 0
7
8 # 2. DFS to find all paths (Exponential)
9 def dfs(r, c, current_path_min):
10 if r == n-1 and c == n-1:
11 max_safeness = max(max_safeness, current_path_min)
12 return
13
14 for neighbor in neighbors(r, c):
15 new_min = min(current_path_min, dist_matrix[neighbor])
16 dfs(neighbor, new_min)
17
18 dfs(0, 0, dist_matrix[0][0])
19 return max_safenessComplexity Analysis: The naive distance calculation takes , which can be in the worst case. Furthermore, the number of paths in a grid is exponential relative to . With , an exponential solution will immediately result in a Time Limit Exceeded (TLE).
Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)
-
Pre-computation (Multi-Source BFS):
- Initialize a distance matrix
distof size with infinity (or -1). - Push all coordinates
(r, c)containing a thief (grid[r][c] == 1) into a queue and set theirdistto 0. - Perform BFS. For each cell, update its unvisited neighbors to have
dist[neighbor] = dist[current] + 1.
- Initialize a distance matrix
-
Pathfinding (Dijkstra's Algorithm):
- Initialize a Max-Heap (Priority Queue).
- Push the starting cell
(0, 0)into the heap. The priority value isdist[0][0]. - Maintain a
visitedmatrix to avoid cycles and redundant processing. - While the heap is not empty:
- Pop the element with the highest safeness factor:
(current_safeness, r, c). - If
(r, c)is the destination(n-1, n-1), returncurrent_safeness. - For each valid neighbor
(nr, nc):- Calculate the new path safeness:
new_safe = min(current_safeness, dist[nr][nc]). - If
(nr, nc)has not been visited, mark it as visited and push(new_safe, nr, nc)to the heap.
- Calculate the new path safeness:
- Pop the element with the highest safeness factor:
Execution Flow
Let's trace the algorithm on a simplified grid.
Input Grid:
0 0 1
0 0 0
0 0 0
Thief at (0, 2).
Step 1: Multi-Source BFS
- Queue starts with
[(0, 2)].dist[0][2] = 0. - Expand
(0, 2): Update neighbors(0, 1)and(1, 2)to distance 1. - Expand layer 1: Update neighbors
(0, 0),(1, 1),(2, 2)to distance 2. - Expand layer 2: Update neighbors
(1, 0),(2, 1)to distance 3. - Expand layer 3: Update neighbor
(2, 0)to distance 4.
Resulting Distance Matrix:
2 1 0
3 2 1
4 3 2
Step 2: Modified Dijkstra
- Init: Max-Heap contains
[(2, 0, 0)]. (Value 2 comes fromdist[0][0]). Visited(0, 0). - Pop:
(2, 0, 0). Neighbors:(0, 1)[dist 1],(1, 0)[dist 3].- Push
(min(2, 1), 0, 1)(1, 0, 1). - Push
(min(2, 3), 1, 0)(2, 1, 0). - Heap:
[(2, 1, 0), (1, 0, 1)].
- Push
- Pop:
(2, 1, 0). Neighbors:(2, 0)[dist 4],(1, 1)[dist 2].- Push
(min(2, 4), 2, 0)(2, 2, 0). - Push
(min(2, 2), 1, 1)(2, 1, 1). - Heap:
[(2, 2, 0), (2, 1, 1), (1, 0, 1)].
- Push
- Pop:
(2, 2, 0). Neighbors:(2, 1)[dist 3].- Push
(min(2, 3), 2, 1)(2, 2, 1). - Heap:
[(2, 2, 1), (2, 1, 1), (1, 0, 1)].
- Push
- Pop:
(2, 2, 1). Neighbors:(2, 2)[dist 2].- Push
(min(2, 2), 2, 2)(2, 2, 2). - Heap:
[(2, 2, 2), (2, 1, 1), (1, 0, 1)].
- Push
- Pop:
(2, 2, 2). This is target(n-1, n-1). - Return: 2.
Proof of Correctness
The correctness relies on the greedy choice property of Dijkstra's algorithm.
- Distance Field Accuracy: The Multi-Source BFS guarantees that
dist[r][c]holds the true minimum Manhattan distance to any thief because BFS finds shortest paths in unweighted graphs layer by layer. - Optimal Substructure: The safeness of a path ending at
uis determined bymin(safeness of path to parent, dist[u]). - Greedy Choice: By using a Max-Heap, we always extend the path that currently has the highest bottleneck value. When we first extract the destination node from the priority queue, the value associated with it is guaranteed to be the maximum possible safeness factor. Any other path to the destination would have been extracted later (meaning it has a lower or equal safeness factor) or is an extension of a path with a lower safeness factor.
Pattern Reuse Notes
The combination of grid traversal and Dijkstra's algorithm is a powerful pattern for "bottleneck" or "weighted path" problems.
- LeetCode 743: Network Delay Time: Uses standard Dijkstra to find the minimum time to reach all nodes.
- LeetCode 778: Swim in Rising Water: Identical logic to LeetCode 2812. You minimize the maximum water level encountered (Minimax instead of Maximin).
- LeetCode 1514: Path with Maximum Probability: Uses Dijkstra with a Max-Heap to maximize the product of edge probabilities.
- LeetCode 1631: Path With Minimum Effort: Minimizes the maximum absolute difference in heights between adjacent cells (another Minimax variation).
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 2812
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximumSafenessFactor(vector<vector<int>>& grid) {
10 int n = grid.size();
11 if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0;
12
13 // Step 1: Multi-source BFS to calculate distance to nearest thief
14 vector<vector<int>> dist(n, vector<int>(n, -1));
15 queue<pair<int, int>> q;
16
17 for (int r = 0; r < n; ++r) {
18 for (int c = 0; c < n; ++c) {
19 if (grid[r][c] == 1) {
20 dist[r][c] = 0;
21 q.push({r, c});
22 }
23 }
24 }
25
26 int dr[] = {0, 0, 1, -1};
27 int dc[] = {1, -1, 0, 0};
28
29 while (!q.empty()) {
30 auto [r, c] = q.front();
31 q.pop();
32
33 for (int i = 0; i < 4; ++i) {
34 int nr = r + dr[i];
35 int nc = c + dc[i];
36 if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
37 dist[nr][nc] = dist[r][c] + 1;
38 q.push({nr, nc});
39 }
40 }
41 }
42
43 // Step 2: Dijkstra's Algorithm (Max-Heap) to find max safeness path
44 // Priority Queue stores {safeness, r, c}
45 priority_queue<tuple<int, int, int>> pq;
46 pq.push({dist[0][0], 0, 0});
47
48 // Reuse dist array to mark visited nodes by setting to -1
49 // (or use a separate visited array)
50 vector<vector<bool>> visited(n, vector<bool>(n, false));
51 visited[0][0] = true;
52
53 while (!pq.empty()) {
54 auto [safe, r, c] = pq.top();
55 pq.pop();
56
57 if (r == n - 1 && c == n - 1) return safe;
58
59 for (int i = 0; i < 4; ++i) {
60 int nr = r + dr[i];
61 int nc = c + dc[i];
62
63 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
64 visited[nr][nc] = true;
65 // The path safeness is limited by the smallest value seen so far
66 int newSafe = min(safe, dist[nr][nc]);
67 pq.push({newSafe, nr, nc});
68 }
69 }
70 }
71
72 return 0;
73 }
74};Java Solution for LeetCode 2812
1import java.util.*;
2
3class Solution {
4 public int maximumSafenessFactor(List<List<Integer>> grid) {
5 int n = grid.size();
6 if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) return 0;
7
8 int[][] dist = new int[n][n];
9 for (int[] row : dist) Arrays.fill(row, -1);
10
11 Queue<int[]> q = new LinkedList<>();
12
13 // Step 1: Multi-source BFS
14 for (int r = 0; r < n; r++) {
15 for (int c = 0; c < n; c++) {
16 if (grid.get(r).get(c) == 1) {
17 dist[r][c] = 0;
18 q.offer(new int[]{r, c});
19 }
20 }
21 }
22
23 int[] dr = {0, 0, 1, -1};
24 int[] dc = {1, -1, 0, 0};
25
26 while (!q.isEmpty()) {
27 int[] curr = q.poll();
28 int r = curr[0], c = curr[1];
29
30 for (int i = 0; i < 4; i++) {
31 int nr = r + dr[i];
32 int nc = c + dc[i];
33 if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
34 dist[nr][nc] = dist[r][c] + 1;
35 q.offer(new int[]{nr, nc});
36 }
37 }
38 }
39
40 // Step 2: Dijkstra's Algorithm using Max-Heap
41 // Stores int[]{safeness, r, c}
42 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
43 pq.offer(new int[]{dist[0][0], 0, 0});
44
45 boolean[][] visited = new boolean[n][n];
46 visited[0][0] = true;
47
48 while (!pq.isEmpty()) {
49 int[] curr = pq.poll();
50 int safe = curr[0], r = curr[1], c = curr[2];
51
52 if (r == n - 1 && c == n - 1) return safe;
53
54 for (int i = 0; i < 4; i++) {
55 int nr = r + dr[i];
56 int nc = c + dc[i];
57 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
58 visited[nr][nc] = true;
59 int newSafe = Math.min(safe, dist[nr][nc]);
60 pq.offer(new int[]{newSafe, nr, nc});
61 }
62 }
63 }
64
65 return 0;
66 }
67}Python Solution for LeetCode 2812
1import heapq
2from collections import deque
3
4class Solution:
5 def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
6 n = len(grid)
7 if grid[0][0] == 1 or grid[n-1][n-1] == 1:
8 return 0
9
10 # Step 1: Multi-source BFS to calculate distances
11 dist = [[-1] * n for _ in range(n)]
12 q = deque()
13
14 for r in range(n):
15 for c in range(n):
16 if grid[r][c] == 1:
17 dist[r][c] = 0
18 q.append((r, c))
19
20 dr = [0, 0, 1, -1]
21 dc = [1, -1, 0, 0]
22
23 while q:
24 r, c = q.popleft()
25 for i in range(4):
26 nr, nc = r + dr[i], c + dc[i]
27 if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
28 dist[nr][nc] = dist[r][c] + 1
29 q.append((nr, nc))
30
31 # Step 2: Dijkstra's Algorithm (Max-Heap)
32 # Python's heapq is a min-heap, so we store negative safeness
33 pq = [(-dist[0][0], 0, 0)]
34 visited = set()
35 visited.add((0, 0))
36
37 while pq:
38 safe, r, c = heapq.heappop(pq)
39 safe = -safe # Convert back to positive
40
41 if r == n - 1 and c == n - 1:
42 return safe
43
44 for i in range(4):
45 nr, nc = r + dr[i], c + dc[i]
46 if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
47 visited.add((nr, nc))
48 new_safe = min(safe, dist[nr][nc])
49 heapq.heappush(pq, (-new_safe, nr, nc))
50
51 return 0