Find the Safest Path in a Grid — Problem & Solution
Find the Safest Path in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Safest Path in a Grid is a medium coding problem on arrays, binary search and matrix, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Matrix, Breadth-First Search, Heap, Union Find
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An n × n grid holds 1 where a thief stands and 0 everywhere else. The safeness factor of a path from the top-left cell to the bottom-right cell is the smallest Manhattan distance from any cell on the path to any thief.
Moving only up, down, left or right, return the maximum safeness factor of any such path.
Example 1
Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 0
Explanation: Both corners hold a thief, so every path touches distance 0.
Example 2
Input: grid = [[0,0,1],[0,0,0],[0,0,0]]
Output: 2
Explanation: Going down the left edge and along the bottom keeps a distance of 2.
Example 3
Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
Output: 2
Constraints
1 <= grid.length == n <= 400grid[i].length == ngrid[i][j] is 0 or 1There is at least one thief in the grid.
Hints for Find the Safest Path in a Grid
Hint 1
First find each cell's distance to the nearest thief with a multi-source breadth-first search.
Hint 2
The answer is the largest
ssuch that some path uses only cells of safeness>= s.Hint 3
That property is monotone in
s, so binary search it.
How to solve Find the Safest Path in a Grid
Two stages. A multi-source BFS from all thieves labels each cell with its distance to the nearest one — which is exactly its safeness. Then binary search the threshold s, testing each with an ordinary search restricted to cells of safeness at least s.
Approach
- BFS from every thief at once to fill the safeness grid.
- For a candidate
s, check that both corners have safeness>= sand that a search from the start reaches the end using only such cells. - Binary search the largest
sthat passes.
Why it works
The multi-source BFS gives Manhattan distance for free, because 4-directional BFS distance in an obstacle-free grid is Manhattan distance to the nearest source. The check is monotone — a path safe at s is safe at every smaller threshold — which is what licenses the binary search; 2n is a safe upper bound since no two cells of an n × n grid are further apart.
Complexity
- Time —
O(n² log n) - Space —
O(n²)
Pitfalls
- The safeness of a path is the minimum over its cells, not a sum or an average.
- Both endpoints count towards the path's safeness.
- A thief on a corner forces the answer to 0.
Reference solution
Python
from typing import List
from collections import deque
def maximumSafenessFactor(grid: List[List[int]]) -> int:
n = len(grid)
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
safe = [-1] * (n * n)
q = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
safe[i * n + j] = 0
q.append((i, j))
while q:
r, c = q.popleft()
for di, dj in dirs:
nr, nc = r + di, c + dj
if 0 <= nr < n and 0 <= nc < n and safe[nr * n + nc] < 0:
safe[nr * n + nc] = safe[r * n + c] + 1
q.append((nr, nc))
def can_do(need: int) -> bool:
if safe[0] < need or safe[n * n - 1] < need:
return False
seen = [False] * (n * n)
seen[0] = True
stack = [0]
while stack:
cur = stack.pop()
if cur == n * n - 1:
return True
r, c = divmod(cur, n)
for di, dj in dirs:
nr, nc = r + di, c + dj
if not (0 <= nr < n and 0 <= nc < n):
continue
v = nr * n + nc
if seen[v] or safe[v] < need:
continue
seen[v] = True
stack.append(v)
return False
lo, hi = 0, 2 * n
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if can_do(mid):
lo = mid
else:
hi = mid - 1
return loJava
private static int[] sfSafe;
private static int sfN;
private static boolean sfCanDo(int need) {
int n = sfN;
if (sfSafe[0] < need || sfSafe[n * n - 1] < need) return false;
boolean[] seen = new boolean[n * n];
int[] stack = new int[n * n];
int[] dr = { 1, -1, 0, 0 };
int[] dc = { 0, 0, 1, -1 };
int top = 0;
seen[0] = true;
stack[top++] = 0;
while (top > 0) {
int u = stack[--top];
if (u == n * n - 1) return true;
int r = u / n, c = u % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
int v = nr * n + nc;
if (seen[v] || sfSafe[v] < need) continue;
seen[v] = true;
stack[top++] = v;
}
}
return false;
}
public static int maximumSafenessFactor(int[][] grid) {
int n = grid.length;
sfN = n;
sfSafe = new int[n * n];
Arrays.fill(sfSafe, -1);
int[] dr = { 1, -1, 0, 0 };
int[] dc = { 0, 0, 1, -1 };
int[] q = new int[n * n];
int head = 0, tail = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) { sfSafe[i * n + j] = 0; q[tail++] = i * n + j; }
}
}
while (head < tail) {
int cur = q[head++];
int r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (sfSafe[nr * n + nc] >= 0) continue;
sfSafe[nr * n + nc] = sfSafe[cur] + 1;
q[tail++] = nr * n + nc;
}
}
int lo = 0, hi = 2 * n;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (sfCanDo(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}C++
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = (int) grid.size();
int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };
vector<int> safe(n * n, -1), q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) { safe[i * n + j] = 0; q.push_back(i * n + j); }
}
}
for (size_t head = 0; head < q.size(); head++) {
int cur = q[head];
int r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (safe[nr * n + nc] >= 0) continue;
safe[nr * n + nc] = safe[cur] + 1;
q.push_back(nr * n + nc);
}
}
auto canDo = [&](int need) {
if (safe[0] < need || safe[n * n - 1] < need) return false;
vector<char> seen(n * n, 0);
vector<int> stack = { 0 };
seen[0] = 1;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (u == n * n - 1) return true;
int r = u / n, c = u % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
int v = nr * n + nc;
if (seen[v] || safe[v] < need) continue;
seen[v] = 1;
stack.push_back(v);
}
}
return false;
};
int lo = 0, hi = 2 * n;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canDo(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}JavaScript
var maximumSafenessFactor = function(grid) {
var n = grid.length, i, j, k;
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var safe = [];
for (i = 0; i < n * n; i++) safe.push(-1);
var q = [];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (grid[i][j] === 1) { safe[i * n + j] = 0; q.push(i * n + j); }
}
}
var head = 0;
while (head < q.length) {
var cur = q[head++];
var r = Math.floor(cur / n), c = cur % n;
for (k = 0; k < 4; k++) {
var nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (safe[nr * n + nc] >= 0) continue;
safe[nr * n + nc] = safe[cur] + 1;
q.push(nr * n + nc);
}
}
var canDo = function(need) {
if (safe[0] < need || safe[n * n - 1] < need) return false;
var seen = [];
for (var t = 0; t < n * n; t++) seen.push(false);
seen[0] = true;
var stack = [0];
while (stack.length > 0) {
var u = stack.pop();
if (u === n * n - 1) return true;
var ur = Math.floor(u / n), uc = u % n;
for (var d = 0; d < 4; d++) {
var ar = ur + dr[d], ac = uc + dc[d];
if (ar < 0 || ar >= n || ac < 0 || ac >= n) continue;
var v = ar * n + ac;
if (seen[v] || safe[v] < need) continue;
seen[v] = true;
stack.push(v);
}
}
return false;
};
var lo = 0, hi = 2 * n;
while (lo < hi) {
var mid = lo + Math.floor((hi - lo + 1) / 2);
if (canDo(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search