Find the Safest Path in a Grid

Medium
958.

Find the Safest Path in a Grid

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.

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.
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
 * @return {number}
 */
var maximumSafenessFactor = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Find the Safest Path in a Grid

  1. Hint 1

    First find each cell's distance to the nearest thief with a multi-source breadth-first search.

  2. Hint 2

    The answer is the largest s such that some path uses only cells of safeness >= s.

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

  1. BFS from every thief at once to fill the safeness grid.
  2. 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.
  3. 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

Java

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