Find the Safest Path in a Grid

Medium Graphs Multi source BFS Original on LeetCode

Reported atUberIntuitZomato

Find the Safest Path in a Grid is a medium graphs problem solved with the multi source bfs pattern. The best approach, optimal (multi-source bfs + bucket queue), runs in O(n²) time and O(n²) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (direct distances, try every threshold) up.

Problem

You get an n x n grid where grid[r][c] == 1 marks a cell with a thief and 0 marks an empty cell. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1), moving one step up, down, left or right at a time. Every cell may be visited, including those with thieves.

The safeness of a path is the smallest Manhattan distance |r1 - r2| + |c1 - c2| between any cell on the path (start and end included) and any thief. Return the largest safeness any path can achieve.

Examples

Example 1

Input
grid = [[0,0,1],[0,0,0],[0,0,0]]
Output
2
Why
Walk down the left column and along the bottom row; the closest the path ever gets to the thief at (0, 2) is distance 2, at both ends.

Example 2

Input
grid = [[1,0,0],[0,0,0],[0,0,1]]
Output
0
Why
The start cell holds a thief, so every path has safeness 0.

Example 3

Input
grid = [[0,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]]
Output
1
Why
Both cells next to the start are at distance 1 from the thief at (1, 1), so no path can do better than 1.

Constraints

  • 1 <= n == grid.length == grid[i].length <= 400
  • grid[i][j] is 0 or 1
  • At least one cell holds a thief.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (direct distances, try every threshold)O(n⁴)O(n²)
Better (multi-source BFS + binary search)O(n² log n)O(n²)
Optimal (multi-source BFS + bucket queue)O(n²)O(n²)

1Brute force (direct distances, try every threshold)

TimeO(n⁴)Distances cost O(n² · T) with up to n² thieves, and up to 2n thresholds each run an O(n²) BFS.
SpaceO(n²)The distance grid, the visited grid and the BFS queue.

Compute each cell's distance to the nearest thief by checking every thief. Then try safeness values from the largest possible downward; for each value s, a BFS from the start that only steps on cells with distance >= s tells whether the end is reachable.

  1. Collect all thief cells. For every cell, its distance is the minimum |r - tr| + |c - tc| over all thieves.
  2. Let s start at min(dist[start], dist[end]), the best any path could do.
  3. While s > 0: BFS from (0, 0) through cells with dist >= s; if it reaches (n - 1, n - 1), return s. Otherwise decrease s.
  4. Return 0 (a path with safeness 0 always exists).
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        List<int[]> thieves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) thieves.add(new int[] {i, j});
            }
        }
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int best = Integer.MAX_VALUE;
                for (int[] t : thieves) {
                    best = Math.min(best, Math.abs(i - t[0]) + Math.abs(j - t[1]));
                }
                dist[i][j] = best;
            }
        }
        for (int s = Math.min(dist[0][0], dist[n - 1][n - 1]); s > 0; s--) {
            if (reach(dist, n, s)) return s;
        }
        return 0;
    }

    private boolean reach(int[][] dist, int n, int s) {
        boolean[][] seen = new boolean[n][n];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0, 0});
        seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n - 1 && cur[1] == n - 1) return true;
            for (int[] d : DIRS) {
                int r = cur[0] + d[0], c = cur[1] + d[1];
                if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c] && dist[r][c] >= s) {
                    seen[r][c] = true;
                    q.add(new int[] {r, c});
                }
            }
        }
        return false;
    }
}

3Optimal (multi-source BFS + bucket queue)

TimeO(n²)The BFS is O(n²), each cell is finished once and pushed at most four times, and walking the buckets adds O(n).
SpaceO(n²)The distance grid, the finished flags and the buckets.

After labelling distances, this is a widest-path problem: a path's value is the smallest label on it, and we want the largest such value. Expand cells greedily, always taking a frontier cell with the best path value (like Dijkstra with a max-heap). Path values only go down and are below 2n, so an array of buckets indexed by value replaces the heap: walk the levels from high to low.

  1. Label every cell with its nearest-thief distance using a multi-source BFS.
  2. Create buckets 0..dist[start]; put the start cell in bucket dist[start].
  3. For level from dist[start] down to 0: pop cells from bucket[level]; skip finished ones; mark the cell finished.
  4. If the popped cell is the end, return level.
  5. Otherwise push each unfinished neighbour into bucket[min(level, dist[neighbour])].
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        int[][] dist = new int[n][n];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    dist[i][j] = 0;
                    q.add(new int[] {i, j});
                } else {
                    dist[i][j] = -1;
                }
            }
        }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int r = cur[0] + d[0], c = cur[1] + d[1];
                if (r >= 0 && r < n && c >= 0 && c < n && dist[r][c] == -1) {
                    dist[r][c] = dist[cur[0]][cur[1]] + 1;
                    q.add(new int[] {r, c});
                }
            }
        }
        int top = dist[0][0];
        List<List<Integer>> buckets = new ArrayList<>();
        for (int k = 0; k <= top; k++) buckets.add(new ArrayList<>());
        buckets.get(top).add(0);
        boolean[] done = new boolean[n * n];
        for (int level = top; level >= 0; level--) {
            List<Integer> b = buckets.get(level);
            while (!b.isEmpty()) {
                int cell = b.remove(b.size() - 1);
                if (done[cell]) continue;
                done[cell] = true;
                int r = cell / n, c = cell % n;
                if (r == n - 1 && c == n - 1) return level;
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && !done[nr * n + nc]) {
                        buckets.get(Math.min(level, dist[nr][nc])).add(nr * n + nc);
                    }
                }
            }
        }
        return 0;
    }
}

Edge cases to test

  • A thief on the start or the end cell: the answer is 0
  • A 1 x 1 grid (which must then be the thief itself)
  • The best path is long and winding while the short path passes close to a thief
  • The answer is capped by the start and end cells themselves, even if the middle of the grid is far from every thief

Hints

Hint 1

First find, for every cell, the Manhattan distance to its nearest thief. One BFS that starts from all thieves at once does this in O(n²).

Hint 2

If a path with safeness at least s exists, then one with safeness s - 1 exists too. That monotonic yes/no question can be binary searched, using a BFS that only enters cells with distance >= s.

Hint 3

Even better: treat it as a widest-path problem. Always expand the reachable cell with the largest distance (the path value is the minimum seen so far). Distances are below 2n, so buckets can replace a heap.

FAQ

What is the best time complexity for Find the Safest Path in a Grid?

Optimal (multi-source BFS + bucket queue) runs in O(n²) time and O(n²) extra space. The BFS is O(n²), each cell is finished once and pushed at most four times, and walking the buckets adds O(n).

Which pattern does Find the Safest Path in a Grid use?

It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Pacific Atlantic Water Flow.

Is there a brute force solution for Find the Safest Path in a Grid?

Yes. Brute force (direct distances, try every threshold) takes O(n⁴) time and O(n²) space. Compute each cell's distance to the nearest thief by checking every thief.

Which edge cases should I test for Find the Safest Path in a Grid?

A thief on the start or the end cell: the answer is 0; A 1 x 1 grid (which must then be the thief itself); The best path is long and winding while the short path passes close to a thief; The answer is capped by the start and end cells themselves, even if the middle of the grid is far from every thief.