Find a Safe Walk Through a Grid

Medium
1723.

Find a Safe Walk Through a Grid

Find a Safe Walk Through a Grid is a medium coding problem on arrays, matrix and breadth-first search, asked in Google interviews.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 2 <= m * n
  • 1 <= health <= m + n
  • grid[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} health
 * @return {boolean}
 */
var findSafeWalk = function(grid, health) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 2 <= m * n
  • 1 <= health <= m + n
  • grid[i][j] is 0 or 1

Hints for Find a Safe Walk Through a Grid

  1. 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.

  2. 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.

  3. 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

  1. Set cost[0][0] = grid[0][0] and process cells level by level: the current level holds cells reached at cost d.
  2. From a cell at cost d, a neighbour costs d + grid[neighbour]. If that improves it, a 0-neighbour joins the current level and a 1-neighbour the next level.
  3. Move to the next level when the current one is exhausted.
  4. 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, not cost <= 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] < health

Java

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