Find the Safest Path in a Grid - Solution & Explanation

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.