Find the Safest Path in a Grid
Find the Safest Path in a Grid is a medium graphs problem solved with the multi source bfs pattern.
The best approach, optimal (multi-source bfs + bucket queue), runs in O(n²) time and O(n²) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (direct distances, try every threshold) up.
Problem
You get an n x n grid where grid[r][c] == 1 marks a cell with a thief and 0 marks an empty cell. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1), moving one step up, down, left or right at a time. Every cell may be visited, including those with thieves.
The safeness of a path is the smallest Manhattan distance |r1 - r2| + |c1 - c2| between any cell on the path (start and end included) and any thief. Return the largest safeness any path can achieve.
Examples
Example 1
- Input
grid = [[0,0,1],[0,0,0],[0,0,0]]- Output
2- Why
- Walk down the left column and along the bottom row; the closest the path ever gets to the thief at (0, 2) is distance 2, at both ends.
Example 2
- Input
grid = [[1,0,0],[0,0,0],[0,0,1]]- Output
0- Why
- The start cell holds a thief, so every path has safeness 0.
Example 3
- Input
grid = [[0,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]]- Output
1- Why
- Both cells next to the start are at distance 1 from the thief at (1, 1), so no path can do better than 1.
Constraints
1 <= n == grid.length == grid[i].length <= 400grid[i][j]is0or1- At least one cell holds a thief.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (direct distances, try every threshold) | O(n⁴) | O(n²) |
| Better (multi-source BFS + binary search) | O(n² log n) | O(n²) |
| Optimal (multi-source BFS + bucket queue) | O(n²) | O(n²) |
1Brute force (direct distances, try every threshold)
O(n⁴)Distances cost O(n² · T) with up to n² thieves, and up to 2n thresholds each run an O(n²) BFS.O(n²)The distance grid, the visited grid and the BFS queue.Compute each cell's distance to the nearest thief by checking every thief. Then try safeness values from the largest possible downward; for each value s, a BFS from the start that only steps on cells with distance >= s tells whether the end is reachable.
- Collect all thief cells. For every cell, its distance is the minimum |r - tr| + |c - tc| over all thieves.
- Let s start at min(dist[start], dist[end]), the best any path could do.
- While s > 0: BFS from (0, 0) through cells with dist >= s; if it reaches (n - 1, n - 1), return s. Otherwise decrease s.
- Return 0 (a path with safeness 0 always exists).
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();
List<int[]> thieves = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 1) thieves.add(new int[] {i, j});
}
}
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int best = Integer.MAX_VALUE;
for (int[] t : thieves) {
best = Math.min(best, Math.abs(i - t[0]) + Math.abs(j - t[1]));
}
dist[i][j] = best;
}
}
for (int s = Math.min(dist[0][0], dist[n - 1][n - 1]); s > 0; s--) {
if (reach(dist, n, s)) return s;
}
return 0;
}
private boolean reach(int[][] dist, int n, int s) {
boolean[][] seen = new boolean[n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
seen[0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == n - 1 && cur[1] == n - 1) return true;
for (int[] d : DIRS) {
int r = cur[0] + d[0], c = cur[1] + d[1];
if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c] && dist[r][c] >= s) {
seen[r][c] = true;
q.add(new int[] {r, c});
}
}
}
return false;
}
}class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
thieves = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]
dist = [[min(abs(i - tr) + abs(j - tc) for tr, tc in thieves) for j in range(n)]
for i in range(n)]
def reach(s: int) -> bool:
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and dist[nr][nc] >= s:
seen[nr][nc] = True
q.append((nr, nc))
return False
for s in range(min(dist[0][0], dist[n - 1][n - 1]), 0, -1):
if reach(s):
return s
return 0class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = grid.size();
vector<pair<int, int>> thieves;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) thieves.push_back({i, j});
vector<vector<int>> dist(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int best = INT_MAX;
for (auto& [tr, tc] : thieves) best = min(best, abs(i - tr) + abs(j - tc));
dist[i][j] = best;
}
}
for (int s = min(dist[0][0], dist[n - 1][n - 1]); s > 0; s--) {
if (reach(dist, n, s)) return s;
}
return 0;
}
private:
bool reach(vector<vector<int>>& dist, int n, int s) {
static const int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<vector<bool>> seen(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({0, 0});
seen[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n - 1 && c == n - 1) return true;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && dist[nr][nc] >= s) {
seen[nr][nc] = true;
q.push({nr, nc});
}
}
}
return false;
}
};function maximumSafenessFactor(grid) {
const n = grid.length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const thieves = [];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) thieves.push([i, j]);
const dist = [];
for (let i = 0; i < n; i++) {
dist.push([]);
for (let j = 0; j < n; j++) {
let best = Infinity;
for (const [tr, tc] of thieves) best = Math.min(best, Math.abs(i - tr) + Math.abs(j - tc));
dist[i].push(best);
}
}
const reach = (s) => {
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
seen[0][0] = true;
const q = [[0, 0]];
for (let h = 0; h < q.length; h++) {
const [r, c] = q[h];
if (r === n - 1 && c === n - 1) return true;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && dist[nr][nc] >= s) {
seen[nr][nc] = true;
q.push([nr, nc]);
}
}
}
return false;
};
for (let s = Math.min(dist[0][0], dist[n - 1][n - 1]); s > 0; s--) {
if (reach(s)) return s;
}
return 0;
}2Better (multi-source BFS + binary search)
O(n² log n)The labelling BFS is O(n²); the binary search runs O(log n) reachability checks of O(n²) each.O(n²)The distance grid, the visited grid and the queues.One BFS seeded with every thief at distance 0 labels all cells with their nearest-thief distance in O(n²). Reachability with threshold s is monotonic (if s works, every smaller value works), so binary search the largest s for which a BFS restricted to cells with distance >= s connects the corners.
- Multi-source BFS: put all thieves in the queue with distance 0, then expand level by level, labelling each new cell with its parent's distance + 1.
- Binary search s in [0, min(dist[start], dist[end])].
- For a candidate s, BFS from (0, 0) over cells with dist >= s; move lo up if the end is reached, else move hi down.
- Return lo.
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();
int[][] dist = distances(grid, n);
int lo = 0, hi = Math.min(dist[0][0], dist[n - 1][n - 1]);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (reach(dist, n, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private int[][] distances(List<List<Integer>> grid, int n) {
int[][] dist = new int[n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 1) {
dist[i][j] = 0;
q.add(new int[] {i, j});
} else {
dist[i][j] = -1;
}
}
}
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : DIRS) {
int r = cur[0] + d[0], c = cur[1] + d[1];
if (r >= 0 && r < n && c >= 0 && c < n && dist[r][c] == -1) {
dist[r][c] = dist[cur[0]][cur[1]] + 1;
q.add(new int[] {r, c});
}
}
}
return dist;
}
private boolean reach(int[][] dist, int n, int s) {
boolean[][] seen = new boolean[n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
seen[0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == n - 1 && cur[1] == n - 1) return true;
for (int[] d : DIRS) {
int r = cur[0] + d[0], c = cur[1] + d[1];
if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c] && dist[r][c] >= s) {
seen[r][c] = true;
q.add(new int[] {r, c});
}
}
}
return false;
}
}class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
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 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))
def reach(s: int) -> bool:
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
bq = deque([(0, 0)])
while bq:
r, c = bq.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and dist[nr][nc] >= s:
seen[nr][nc] = True
bq.append((nr, nc))
return False
lo, hi = 0, min(dist[0][0], dist[n - 1][n - 1])
while lo < hi:
mid = (lo + hi + 1) // 2
if reach(mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> dist(n, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) { dist[i][j] = 0; q.push({i, j}); }
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
int lo = 0, hi = min(dist[0][0], dist[n - 1][n - 1]);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (reach(dist, n, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private:
const int DR[4] = {1, -1, 0, 0};
const int DC[4] = {0, 0, 1, -1};
bool reach(vector<vector<int>>& dist, int n, int s) {
vector<vector<bool>> seen(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({0, 0});
seen[0][0] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == n - 1 && c == n - 1) return true;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && dist[nr][nc] >= s) {
seen[nr][nc] = true;
q.push({nr, nc});
}
}
}
return false;
}
};function maximumSafenessFactor(grid) {
const n = grid.length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dist = Array.from({ length: n }, () => new Array(n).fill(-1));
const q = [];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) { dist[i][j] = 0; q.push([i, j]); }
for (let h = 0; h < q.length; h++) {
const [r, c] = q[h];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] === -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push([nr, nc]);
}
}
}
const reach = (s) => {
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
seen[0][0] = true;
const bq = [[0, 0]];
for (let h = 0; h < bq.length; h++) {
const [r, c] = bq[h];
if (r === n - 1 && c === n - 1) return true;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && dist[nr][nc] >= s) {
seen[nr][nc] = true;
bq.push([nr, nc]);
}
}
}
return false;
};
let lo = 0, hi = Math.min(dist[0][0], dist[n - 1][n - 1]);
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (reach(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}3Optimal (multi-source BFS + bucket queue)
O(n²)The BFS is O(n²), each cell is finished once and pushed at most four times, and walking the buckets adds O(n).O(n²)The distance grid, the finished flags and the buckets.After labelling distances, this is a widest-path problem: a path's value is the smallest label on it, and we want the largest such value. Expand cells greedily, always taking a frontier cell with the best path value (like Dijkstra with a max-heap). Path values only go down and are below 2n, so an array of buckets indexed by value replaces the heap: walk the levels from high to low.
- Label every cell with its nearest-thief distance using a multi-source BFS.
- Create buckets 0..dist[start]; put the start cell in bucket dist[start].
- For level from dist[start] down to 0: pop cells from bucket[level]; skip finished ones; mark the cell finished.
- If the popped cell is the end, return level.
- Otherwise push each unfinished neighbour into bucket[min(level, dist[neighbour])].
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();
int[][] dist = new int[n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid.get(i).get(j) == 1) {
dist[i][j] = 0;
q.add(new int[] {i, j});
} else {
dist[i][j] = -1;
}
}
}
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : DIRS) {
int r = cur[0] + d[0], c = cur[1] + d[1];
if (r >= 0 && r < n && c >= 0 && c < n && dist[r][c] == -1) {
dist[r][c] = dist[cur[0]][cur[1]] + 1;
q.add(new int[] {r, c});
}
}
}
int top = dist[0][0];
List<List<Integer>> buckets = new ArrayList<>();
for (int k = 0; k <= top; k++) buckets.add(new ArrayList<>());
buckets.get(top).add(0);
boolean[] done = new boolean[n * n];
for (int level = top; level >= 0; level--) {
List<Integer> b = buckets.get(level);
while (!b.isEmpty()) {
int cell = b.remove(b.size() - 1);
if (done[cell]) continue;
done[cell] = true;
int r = cell / n, c = cell % n;
if (r == n - 1 && c == n - 1) return level;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr * n + nc]) {
buckets.get(Math.min(level, dist[nr][nc])).add(nr * n + nc);
}
}
}
}
return 0;
}
}class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
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 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))
top = dist[0][0]
buckets = [[] for _ in range(top + 1)]
buckets[top].append(0)
done = [False] * (n * n)
for level in range(top, -1, -1):
b = buckets[level]
while b:
cell = b.pop()
if done[cell]:
continue
done[cell] = True
r, c = divmod(cell, n)
if r == n - 1 and c == n - 1:
return level
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not done[nr * n + nc]:
buckets[min(level, dist[nr][nc])].append(nr * n + nc)
return 0class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = grid.size();
const int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<vector<int>> dist(n, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) { dist[i][j] = 0; q.push({i, j}); }
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
int top = dist[0][0];
vector<vector<int>> buckets(top + 1);
buckets[top].push_back(0);
vector<bool> done(n * n, false);
for (int level = top; level >= 0; level--) {
vector<int>& b = buckets[level];
while (!b.empty()) {
int cell = b.back();
b.pop_back();
if (done[cell]) continue;
done[cell] = true;
int r = cell / n, c = cell % n;
if (r == n - 1 && c == n - 1) return level;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr * n + nc]) {
buckets[min(level, dist[nr][nc])].push_back(nr * n + nc);
}
}
}
}
return 0;
}
};function maximumSafenessFactor(grid) {
const n = grid.length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dist = Array.from({ length: n }, () => new Array(n).fill(-1));
const q = [];
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) { dist[i][j] = 0; q.push([i, j]); }
for (let h = 0; h < q.length; h++) {
const [r, c] = q[h];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] === -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push([nr, nc]);
}
}
}
const top = dist[0][0];
const buckets = Array.from({ length: top + 1 }, () => []);
buckets[top].push(0);
const done = new Uint8Array(n * n);
for (let level = top; level >= 0; level--) {
const b = buckets[level];
while (b.length > 0) {
const cell = b.pop();
if (done[cell]) continue;
done[cell] = 1;
const r = Math.floor(cell / n), c = cell % n;
if (r === n - 1 && c === n - 1) return level;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr * n + nc]) {
buckets[Math.min(level, dist[nr][nc])].push(nr * n + nc);
}
}
}
}
return 0;
}Edge cases to test
- A thief on the start or the end cell: the answer is 0
- A 1 x 1 grid (which must then be the thief itself)
- The best path is long and winding while the short path passes close to a thief
- The answer is capped by the start and end cells themselves, even if the middle of the grid is far from every thief
Hints
Hint 1
First find, for every cell, the Manhattan distance to its nearest thief. One BFS that starts from all thieves at once does this in O(n²).
Hint 2
If a path with safeness at least s exists, then one with safeness s - 1 exists too. That monotonic yes/no question can be binary searched, using a BFS that only enters cells with distance >= s.
Hint 3
Even better: treat it as a widest-path problem. Always expand the reachable cell with the largest distance (the path value is the minimum seen so far). Distances are below 2n, so buckets can replace a heap.
FAQ
What is the best time complexity for Find the Safest Path in a Grid?
Optimal (multi-source BFS + bucket queue) runs in O(n²) time and O(n²) extra space. The BFS is O(n²), each cell is finished once and pushed at most four times, and walking the buckets adds O(n).
Which pattern does Find the Safest Path in a Grid use?
It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Pacific Atlantic Water Flow.
Is there a brute force solution for Find the Safest Path in a Grid?
Yes. Brute force (direct distances, try every threshold) takes O(n⁴) time and O(n²) space. Compute each cell's distance to the nearest thief by checking every thief.
Which edge cases should I test for Find the Safest Path in a Grid?
A thief on the start or the end cell: the answer is 0; A 1 x 1 grid (which must then be the thief itself); The best path is long and winding while the short path passes close to a thief; The answer is capped by the start and end cells themselves, even if the middle of the grid is far from every thief.