Find the Safest Path in a Grid

Medium · Heap / Priority Queue · Explanation and code example

Breadth First Search (0-1 BFS)

How it works

0-1 BFS is an optimization when edge weights are only 0 or 1. Here we adapt it: moving to a neighbor with the same or better safeness has cost 0, while moving to a neighbor with worse safeness has cost 1 (we are forced to accept a lower minimum). By adding zero-cost moves to the front and cost-1 moves to the back of a deque, we process cells in order of decreasing safeness factor.

Steps

  1. Precompute minDist using multi-source BFS.
  2. Initialize safeFactor[0] = min(minDist[0][0], minDist[N-1][N-1]) and track the running result res.
  3. Use a deque starting with cell 0.
  4. For each cell popped:
    • Update res = min(res, safeFactor[node]).
    • If destination reached, break.
    • For each unvisited neighbor:
      • Compute its safeness as min(safeFactor[current], minDist[neighbor]).
      • If it maintains the current result, add to front (zero cost); otherwise add to back.
  5. Return res.

Complexity

  • Time complexity: O(n ^ 2)
  • Space complexity: O(n ^ 2)

Things to watch for

Using Single-Source BFS Instead of Multi-Source BFS

To compute the minimum distance from each cell to the nearest thief, you must start BFS from all thief cells simultaneously. A common mistake is running separate BFS from each thief and taking the minimum, which results in O(n^4) time complexity instead of O(n^2).

Confusing Min-Heap with Max-Heap in Dijkstra

Since we want to maximize the minimum distance (safeness factor), we need a max-heap to always process the path with the highest current safeness first. Using a min-heap (standard Dijkstra) will find the path with the lowest safeness instead, giving incorrect results.

Forgetting to Check Start and End Cell Constraints

The safeness of any path is bounded by the minimum distance at both the start cell (0,0) and the destination cell (N-1, N-1). If either cell contains a thief (distance 0), the maximum safeness is 0 regardless of the path taken. Some solutions skip this edge case check.

Python code example

from collections import deque

class Solution:
    def maximumSafenessFactor(self, grid):
        N = len(grid)
        minDist = grid
        directions = [0, 1, 0, -1, 0]

        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    q.append(r * N + c)
                    minDist[r][c] = 0
                else:
                    minDist[r][c] = -1

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                if 0 <= r2 < N and 0 <= c2 < N and minDist[r2][c2] == -1:
                    minDist[r2][c2] = minDist[r][c] + 1
                    q.append(r2 * N + c2)

        safeFactor = [-1] * (N * N)
        res = safeFactor[0] = min(minDist[N - 1][N - 1], minDist[0][0])
        q.append(0)

        while q:
            node = q.popleft()
            r, c = divmod(node, N)
            res = min(res, safeFactor[node])
            if r == N - 1 and c == N - 1:
                break

            for i in range(4):
                r2, c2 = r + directions[i], c + directions[i + 1]
                node2 = r2 * N + c2
                if 0 <= r2 < N and 0 <= c2 < N and safeFactor[node2] == -1:
                    safeFactor[node2] = min(safeFactor[node], minDist[r2][c2])
                    if safeFactor[node2] < res:
                        q.append(node2)
                    else:
                        q.appendleft(node2)

        return res

C++ code example

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int N = grid.size();
        vector<vector<int>>& minDist = grid;
        constexpr int directions[5] = {0, 1, 0, -1, 0};

        deque<int> q;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (grid[r][c] == 1) {
                    q.push_back(r * N + c);
                    minDist[r][c] = 0;
                } else {
                    minDist[r][c] = -1;
                }
            }
        }

        while (!q.empty()) {
            int node = q.front(); q.pop_front();
            int r = node / N, c = node % N;
            for (int i = 0; i < 4; i++) {
                int r2 = r + directions[i], c2 = c + directions[i + 1];
                if (r2 >= 0 && c2 >= 0 && r2 < N && c2 < N && minDist[r2][c2] == -1) {
                    minDist[r2][c2] = minDist[r][c] + 1;
                    q.push_back(r2 * N + c2);
                }
            }
        }

        vector<int> safeFactor(N * N, -1);
        int res = safeFactor[0] = min(minDist[N - 1][N - 1], minDist[0][0]);
        q.push_back(0);

        while (!q.empty()) {
            int node = q.front(); q.pop_front();
            int r = node / N, c = node % N;
            res = min(res, safeFactor[node]);
            if (r == N - 1 && c == N - 1) {
                break;
            }

            for (int i = 0; i < 4; i++) {
                int r2 = r + directions[i], c2 = c + directions[i + 1], node2 = r2 * N + c2;
                if (r2 >= 0 && c2 >= 0 && r2 < N && c2 < N && safeFactor[node2] == -1) {
                    safeFactor[node2] = min(safeFactor[node], minDist[r2][c2]);
                    if (safeFactor[node2] < res) {
                        q.push_back(node2);
                    } else {
                        q.push_front(node2);
                    }
                }
            }
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations