Find a Safe Walk Through a Grid — Problem & Solution
Find a Safe Walk Through a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find a Safe Walk Through a Grid is a medium coding problem on arrays, matrix and breadth-first search, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Breadth-First Search, Graph, Heap, Shortest Path
- Asked at: Google
- 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
You are given an m x n binary matrix grid and an integer health.
You start in the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1), moving one step at a time up, down, left or right, never leaving the grid. A cell with grid[i][j] = 1 is unsafe: every time you are in it — including the start and the destination — your health drops by 1.
Return true if you can reach the destination with health at least 1, and false otherwise.
Example 1
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
Output: true
Explanation: Go down the left column, along the bottom to the middle, up and around through the top-right: every cell on that route is 0.
Example 2
Input: grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
Output: false
Explanation: Every route crosses at least three unsafe cells, which would bring health to 0.
Example 3
Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
Output: true
Explanation: Any shortest route steps on four unsafe cells (the start and the end included), leaving health 1.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 502 <= m * n1 <= health <= m + ngrid[i][j] is 0 or 1
Hints for Find a Safe Walk Through a Grid
Hint 1
Only the number of unsafe cells on the route matters, not its length — so find the route that visits the fewest 1-cells.
Hint 2
That is a shortest path where entering a cell costs
grid[i][j](0 or 1), and the start cell's own value counts too.Hint 3
With edge weights 0 and 1, a 0-1 BFS (or Dijkstra) finds the minimum cost; the walk is safe exactly when that cost is less than
health.
How to solve Find a Safe Walk Through a Grid
Treat each cell's value as the price of standing in it. The best route minimises the total price, which is a shortest-path problem with weights 0 and 1, solved by 0-1 BFS in linear time.
Approach
- Set
cost[0][0] = grid[0][0]and process cells level by level: the current level holds cells reached at costd. - From a cell at cost
d, a neighbour costsd + grid[neighbour]. If that improves it, a 0-neighbour joins the current level and a 1-neighbour the next level. - Move to the next level when the current one is exhausted.
- Return
cost[m - 1][n - 1] < health.
Why it works
Processing costs in increasing order is Dijkstra's invariant: a cell taken from level d cannot be improved by anything processed later, because every later cell already costs at least d and edges never have negative weight. Two buckets are enough because an edge adds at most 1.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- The start and the destination count — a grid whose corner is 1 already costs health there.
- Health must stay at least 1, so the condition is
cost < health, notcost <= health. - A plain BFS counting steps finds the shortest route, not the safest one.
Reference solution
Python
from typing import List
def findSafeWalk(grid: List[List[int]], health: int) -> bool:
m, n = len(grid), len(grid[0])
total = m * n
cost = [total + 1] * total
cost[0] = grid[0][0]
cur = [0]
d = cost[0]
while cur:
nxt = []
i = 0
while i < len(cur):
x = cur[i]
i += 1
if cost[x] != d:
continue
r, c = divmod(x, n)
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n:
y = nr * n + nc
nd = d + grid[nr][nc]
if nd < cost[y]:
cost[y] = nd
(cur if grid[nr][nc] == 0 else nxt).append(y)
cur = nxt
d += 1
return cost[total - 1] < healthJava
public static boolean findSafeWalk(int[][] grid, int health) {
int m = grid.length, n = grid[0].length, total = m * n;
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
int[] cost = new int[total];
Arrays.fill(cost, total + 1);
cost[0] = grid[0][0];
int[] cur = new int[total + 1], next = new int[total + 1];
int curLen = 0;
cur[curLen++] = 0;
int d = cost[0];
while (curLen > 0) {
int nextLen = 0;
for (int h = 0; h < curLen; h++) {
int x = cur[h];
if (cost[x] != d) continue;
int r = x / n, c = x % n;
for (int k = 0; k < 4; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int y = nr * n + nc, nd = d + grid[nr][nc];
if (nd < cost[y]) {
cost[y] = nd;
if (grid[nr][nc] == 0) cur[curLen++] = y; else next[nextLen++] = y;
}
}
}
int[] t = cur; cur = next; next = t;
curLen = nextLen;
d++;
}
return cost[total - 1] < health;
}C++
bool findSafeWalk(vector<vector<int>>& grid, int health) {
int m = grid.size(), n = grid[0].size(), total = m * n;
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<int> cost(total, total + 1);
cost[0] = grid[0][0];
vector<int> cur = {0};
int d = cost[0];
while (!cur.empty()) {
vector<int> next;
for (size_t h = 0; h < cur.size(); h++) {
int x = cur[h];
if (cost[x] != d) continue;
int r = x / n, c = x % n;
for (int k = 0; k < 4; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int y = nr * n + nc, nd = d + grid[nr][nc];
if (nd < cost[y]) {
cost[y] = nd;
if (grid[nr][nc] == 0) cur.push_back(y); else next.push_back(y);
}
}
}
cur.swap(next);
d++;
}
return cost[total - 1] < health;
}JavaScript
var findSafeWalk = function(grid, health) {
var m = grid.length, n = grid[0].length, total = m * n;
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
var cost = [];
for (var i = 0; i < total; i++) cost.push(total + 1);
cost[0] = grid[0][0];
var cur = [0], d = cost[0];
while (cur.length > 0) {
var next = [];
for (var h = 0; h < cur.length; h++) {
var x = cur[h];
if (cost[x] !== d) continue;
var r = Math.floor(x / n), c = x % n;
for (var k = 0; k < 4; k++) {
var nr = r + DR[k], nc = c + DC[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
var y = nr * n + nc, nd = d + grid[nr][nc];
if (nd < cost[y]) {
cost[y] = nd;
if (grid[nr][nc] === 0) cur.push(y); else next.push(y);
}
}
}
cur = next;
d++;
}
return cost[total - 1] < health;
};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 · Matrix and Grid Traversal