Find the Safest Path in a Grid — Medium Problem & Solution

An n × n grid holds 1 where a thief stands and 0 everywhere else.

Difficulty: Medium
Topics: Arrays, Matrix, Binary Search, 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 <= 400
grid[i].length == n
grid[i][j] is 0 or 1
There is at least one thief in the grid.

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 >= s and that a search from the start reaches the end using only such cells.
Binary search the largest s that 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue