Watch 10 video solutions for Find the Safest Path in a Grid, a medium level problem involving Array, Binary Search, Breadth-First Search. This walkthrough by NeetCodeIO has 19,267 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:
grid[r][c] = 1grid[r][c] = 0You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.
The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.
Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).
An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.
The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.
Example 1:
Input: grid = [[1,0,0],[0,0,0],[0,0,1]] Output: 0 Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
Example 2:
Input: grid = [[0,0,1],[0,0,0],[0,0,0]] Output: 2 Explanation: The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor.
Example 3:
Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]] Output: 2 Explanation: The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2. - The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor.
Constraints:
1 <= grid.length == n <= 400grid[i].length == ngrid[i][j] is either 0 or 1.grid.Problem Overview: You are given an n x n grid where cells containing 1 represent thieves. The goal is to travel from the top‑left cell to the bottom‑right cell while maximizing the minimum distance to any thief along the path. The safety of a path equals the smallest distance from any cell on that path to the nearest thief.
Approach 1: BFS with Distance Preprocessing (Multi‑Source BFS + Search) (Time: O(n² log n), Space: O(n²))
The key observation: instead of evaluating safety during traversal, first compute how safe every cell is. Run a multi‑source Breadth‑First Search starting from all thief cells simultaneously. This fills a matrix where dist[r][c] stores the shortest distance to the nearest thief. Once this preprocessing is done, the task becomes finding a path that maximizes the minimum value in dist.
To achieve that, perform a search on the answer. Use binary search on the possible safeness factor. For a candidate value k, run BFS from (0,0) and only step into cells whose dist value is at least k. If you can reach (n‑1,n‑1), that safeness level is feasible. Binary search finds the maximum valid value.
This approach separates the problem into two clean phases: computing distances with multi‑source BFS and validating paths with BFS. It is efficient because each grid cell is processed a constant number of times, and the binary search range is limited by the grid size.
Approach 2: Bidirectional BFS on the Safety Graph (Time: O(n²), Space: O(n²))
Another perspective treats the grid as a graph where each cell has a safety score from the preprocessing step. Instead of exploring from only the start, run BFS simultaneously from both the start and the destination. Each frontier expands through cells that satisfy the minimum safety constraint, and the search stops when the two frontiers meet.
Bidirectional BFS reduces the explored state space compared to a single-direction traversal because both ends converge toward the middle. This often improves practical performance on large grids where a single BFS would visit many unnecessary cells.
The preprocessing phase remains identical: compute the nearest‑thief distance for every cell using multi‑source BFS. After that, the bidirectional search checks connectivity under a chosen safety threshold while expanding from both sides.
Recommended for interviews: The multi‑source BFS + binary search solution is the one most interviewers expect. It demonstrates strong understanding of matrix traversal, BFS layering, and transforming a max‑min path problem into a monotonic search. Mentioning brute reasoning (checking paths directly) shows problem exploration, but implementing the BFS distance preprocessing with binary search shows the algorithmic insight interviewers look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Distance Preprocessing + Binary Search | O(n² log n) | O(n²) | General solution for interview settings. Clean separation between computing safety distances and validating paths. |
| Bidirectional BFS with Safety Constraints | O(n²) | O(n²) | Useful when reducing search space matters; explores from both start and destination simultaneously. |