# Find the Safest Path in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-safest-path-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/find-the-safest-path-in-a-grid
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [IMC](https://scaleengineer.com/companies/imc)
---
## Problem
You are given a **0-indexed** 2D matrix `grid` of size `n x n`, where `(r, c)` represents:

* A cell containing a thief if `grid[r][c] = 1`
* An empty cell if `grid[r][c] = 0`

You 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:**

![](https://assets.glich.co/dsa/find-the-safest-path-in-a-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-the-safest-path-in-a-grid/image1.png) 

**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:**

![](https://assets.glich.co/dsa/find-the-safest-path-in-a-grid/image2.png) 

**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 <= 400`
* `grid[i].length == n`
* `grid[i][j]` is either `0` or `1`.
* There is at least one thief in the `grid`.

# Approaches
## Binary Search on Safeness Factor
This approach first calculates the "safeness" of every cell, which is its minimum Manhattan distance to any thief. This is done using a multi-source Breadth-First Search (BFS) starting from all thief cells simultaneously. After this pre-computation, the problem becomes: find a path from (0,0) to (n-1, n-1) that maximizes the minimum safeness value of any cell on the path. This "max-min" structure is a classic indicator for binary searching on the answer. We can binary search for the maximum possible safeness factor, `S`. For a given `S`, we check if a path exists from (0,0) to (n-1, n-1) using only cells with a safeness value of at least `S`. This check can be performed with another BFS or DFS.
**Time:** O(n^2 * log(n)) - The initial multi-source BFS to calculate safeness for all cells takes O(n^2). The binary search performs O(log(D)) iterations, where D is the maximum possible safeness (at most 2n). Each iteration involves a BFS check that takes O(n^2) time. Thus, the total complexity is O(n^2 + n^2 * log(n)) which simplifies to O(n^2 * log(n)). · **Space:** O(n^2) - This is required to store the `safeness` matrix. Additional space is used for the queues and visited sets in the BFS traversals, which is also O(n^2).
**Pros:** Conceptually straightforward, breaking the problem into two standard subproblems (multi-source BFS and binary search).; Relatively easy to implement correctly.
**Cons:** Not the most optimal solution in terms of time complexity.; The repeated BFS checks inside the binary search can be inefficient as they re-explore parts of the grid multiple times.
### Explanation
The core idea is to separate the problem into two main parts. First, we determine the safeness of each individual cell. The safeness of a cell is its minimum Manhattan distance to any thief. This can be efficiently computed for all cells at once using a multi-source BFS, where all thief cells are the initial sources. 

Once we have the `safeness` value for every cell, the problem transforms into finding a path from the top-left to the bottom-right corner such that the minimum `safeness` value encountered along the path is maximized. This property—maximizing a minimum—is monotonic. If a path with a safeness factor of `S` exists, a path with a factor of `S-1` also exists. This allows us to binary search for the answer. For each potential safeness factor `mid` we test, we run a simple BFS/DFS to see if a valid path exists. A path is valid if all its cells have a safeness value of at least `mid`.

```java
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int n;

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();

        // 1. Pre-compute safeness for each cell using multi-source BFS
        int[][] safeness = new int[n][n];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    q.offer(new int[]{i, j});
                    safeness[i][j] = 0;
                } else {
                    safeness[i][j] = -1; // Mark as unvisited
                }
            }
        }

        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            level++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int newR = curr[0] + dir[0];
                    int newC = curr[1] + dir[1];
                    if (newR >= 0 && newR < n && newC >= 0 && newC < n && safeness[newR][newC] == -1) {
                        safeness[newR][newC] = level;
                        q.offer(new int[]{newR, newC});
                    }
                }
            }
        }

        // 2. Binary search for the maximum safeness factor
        int low = 0;
        int high = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                high = Math.max(high, safeness[i][j]);
            }
        }
        
        int ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPathPossible(safeness, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    // Helper function to check if a path exists with at least `minSafeness`
    private boolean isPathPossible(int[][] safeness, int minSafeness) {
        if (safeness[0][0] < minSafeness || safeness[n - 1][n - 1] < minSafeness) {
            return false;
        }

        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];

        q.offer(new int[]{0, 0});
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) {
                return true;
            }

            for (int[] dir : dirs) {
                int newR = curr[0] + dir[0];
                int newC = curr[1] + dir[1];

                if (newR >= 0 && newR < n && newC >= 0 && newC < n && !visited[newR][newC] && safeness[newR][newC] >= minSafeness) {
                    visited[newR][newC] = true;
                    q.offer(new int[]{newR, newC});
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- **Pre-computation (Multi-source BFS):**
  - Create a `safeness` matrix of the same size as the grid, initialized to a large value.
  - Create a queue and add the coordinates of all thief cells (`grid[r][c] == 1`). Set their safeness to 0.
  - Perform a BFS starting from all thieves simultaneously. In each step, dequeue a cell, and for its unvisited neighbors, update their safeness to `current_safeness + 1` and enqueue them. This populates the `safeness` matrix with the minimum Manhattan distance from each cell to the nearest thief.
- **Binary Search on the Answer:**
  - Set search boundaries `low = 0` and `high` to the maximum possible safeness (e.g., `2n`). Store the best result in a variable `ans`.
  - While `low <= high`:
    - Calculate `mid = low + (high - low) / 2`.
    - **Check feasibility:** Use another BFS or DFS to check if a path exists from `(0, 0)` to `(n-1, n-1)` using only cells `(r, c)` where `safeness[r][c] >= mid`.
    - If a path is possible for `mid`, it means `mid` is a potential answer. We try for a better (larger) one: `ans = mid`, `low = mid + 1`.
    - If no path is possible, we must try a smaller safeness factor: `high = mid - 1`.
- **Return `ans`**.

## Multi-source BFS and Optimized Dijkstra's Algorithm
This approach also starts with the same pre-computation step: a multi-source BFS to calculate the safeness of each cell. The second step, instead of binary searching, re-frames the problem as finding a "widest path" or "bottleneck path" on the grid. Each cell `(r, c)` is a node with a value `safeness[r][c]`. We want to find a path from `(0, 0)` to `(n-1, n-1)` where the minimum value of any node on the path is maximized. This can be solved efficiently using a modified version of Dijkstra's algorithm. Instead of minimizing a sum, we maximize a minimum. A priority queue is used to always explore paths with higher safeness first. By using a bucket-based data structure instead of a binary heap priority queue (since safeness values are integers in a limited range), we can optimize the Dijkstra part to run in linear time relative to the number of cells, leading to an overall optimal solution.
**Time:** O(n^2) - The multi-source BFS for pre-computation takes O(n^2). The optimized Dijkstra's algorithm using buckets also runs in O(n^2) because each cell is enqueued and processed exactly once. The total time is O(n^2 + n^2) = O(n^2). · **Space:** O(n^2) - Space is needed for the `safeness` matrix, the `max_path_safeness` matrix, and the `buckets` data structure. The number of elements across all buckets is at most O(n^2).
**Pros:** Most efficient solution with an optimal time complexity.; Solves the problem in a single pass after the pre-computation step, avoiding the repeated checks of the binary search approach.
**Cons:** The logic for the modified Dijkstra, especially with the bucket optimization, can be more complex to reason about and implement compared to the binary search approach.
### Explanation
This approach provides the most optimal time complexity. Like the previous method, it begins by pre-calculating the safeness of every cell using a multi-source BFS. The key difference lies in the second phase. Instead of binary search, we treat the grid as a graph where we want to find a path from `(0,0)` to `(n-1,n-1)` that maximizes the bottleneck capacity (the minimum safeness on the path).

This is a classic application for a modified Dijkstra's algorithm. In our version, the "distance" we track is the maximum possible safeness factor of a path from the source to the current cell. We use a priority queue to always expand the path with the highest current safeness factor. A standard binary heap would yield an O(n^2 * log(n)) solution. However, since the priorities (safeness values) are integers within a limited range (0 to ~2n), we can use an array of buckets instead of a heap. We iterate through the buckets from highest safeness to lowest. This effectively simulates a max-priority queue with O(1) amortized time for finding and extracting the max element, leading to an overall O(n^2) time complexity.

```java
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int n;

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        
        // 1. Pre-compute safeness for each cell using multi-source BFS
        int[][] safeness = new int[n][n];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    q.offer(new int[]{i, j});
                    safeness[i][j] = 0;
                } else {
                    safeness[i][j] = -1; // Mark as unvisited
                }
            }
        }

        int maxSafenessValue = 0;
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            level++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int newR = curr[0] + dir[0];
                    int newC = curr[1] + dir[1];
                    if (newR >= 0 && newR < n && newC >= 0 && newC < n && safeness[newR][newC] == -1) {
                        safeness[newR][newC] = level;
                        maxSafenessValue = Math.max(maxSafenessValue, level);
                        q.offer(new int[]{newR, newC});
                    }
                }
            }
        }

        // 2. Optimized Dijkstra using buckets
        List<int[]>[] buckets = new ArrayList[maxSafenessValue + 1];
        for (int i = 0; i <= maxSafenessValue; i++) {
            buckets[i] = new ArrayList<>();
        }

        int[][] maxPathSafeness = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(maxPathSafeness[i], -1);
        }

        maxPathSafeness[0][0] = safeness[0][0];
        buckets[safeness[0][0]].add(new int[]{0, 0});

        for (int s = maxSafenessValue; s >= 0; s--) {
            int bucketIdx = 0;
            while (bucketIdx < buckets[s].size()) {
                int[] curr = buckets[s].get(bucketIdx++);
                int r = curr[0];
                int c = curr[1];

                if (r == n - 1 && c == n - 1) return s;

                for (int[] dir : dirs) {
                    int newR = r + dir[0];
                    int newC = c + dir[1];

                    if (newR >= 0 && newR < n && newC >= 0 && newC < n) {
                        int newPathSafeness = Math.min(s, safeness[newR][newC]);
                        if (newPathSafeness > maxPathSafeness[newR][newC]) {
                            maxPathSafeness[newR][newC] = newPathSafeness;
                            buckets[newPathSafeness].add(new int[]{newR, newC});
                        }
                    }
                }
            }
        }
        
        return 0; // Path from (0,0) to (n-1,n-1) is always possible
    }
}
```
### Algorithm
- **Pre-computation (Multi-source BFS):**
  - Same as the previous approach. Calculate the `safeness` matrix for all cells in O(n^2) time.
- **Optimized Dijkstra's Algorithm (using Buckets):**
  - Create a `max_path_safeness` matrix to store the maximum safeness of a path to each cell, initialized to -1.
  - Create an array of lists called `buckets`. `buckets[s]` will store all cells `(r, c)` that are part of a path with safeness `s`. The size of this array will be up to the maximum safeness value found.
  - Start with cell `(0, 0)`. Its initial path safeness is `s_start = safeness[0][0]`. Add `(0, 0)` to `buckets[s_start]` and set `max_path_safeness[0][0] = s_start`.
  - Iterate `s` from the maximum possible safeness down to 0.
  - For each `s`, process all cells currently in `buckets[s]`.
  - For each cell `(r, c)` from `buckets[s]`:
    - If `(r, c)` is the destination `(n-1, n-1)`, we have found the maximum safeness, so return `s`.
    - For each neighbor `(nr, nc)`:
      - Calculate the new path safeness: `new_s = min(s, safeness[nr][nc])`.
      - If `new_s > max_path_safeness[nr][nc]`, update `max_path_safeness[nr][nc] = new_s` and add `(nr, nc)` to `buckets[new_s]`.

# Solutions
### Java

```java
class Solution {
public
  int maximumSafenessFactor(List<List<Integer>> grid) {
    int n = grid.size();
    if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
      return 0;
    }
    Deque<int[]> q = new ArrayDeque<>();
    int[][] dist = new int[n][n];
    final int inf = 1 << 30;
    for (int[] d : dist) {
      Arrays.fill(d, inf);
    }
    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.offer(new int[]{i, j});
        }
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int[] p = q.poll();
      int i = p[0], j = p[1];
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == inf) {
          dist[x][y] = dist[i][j] + 1;
          q.offer(new int[]{x, y});
        }
      }
    }
    List<int[]> t = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        t.add(new int[]{dist[i][j], i, j});
      }
    }
    t.sort((a, b)->Integer.compare(b[0], a[0]));
    UnionFind uf = new UnionFind(n * n);
    for (int[] p : t) {
      int d = p[0], i = p[1], j = p[2];
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d) {
          uf.union(i * n + j, x * n + y);
        }
      }
      if (uf.find(0) == uf.find(n * n - 1)) {
        return d;
      }
    }
    return 0;
  }
} class UnionFind {
public
  int[] p;
public
  int n;
public
  UnionFind(int n) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    this.n = n;
  }
public
  boolean union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) {
      return false;
    }
    p[pa] = pb;
    --n;
    return true;
  }
public
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) return false ; p [ pa ] = pb ; -- n ; return true ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: int maximumSafenessFactor ( vector < vector < int >>& grid ) { int n = grid . size (); if ( grid [ 0 ][ 0 ] || grid [ n - 1 ][ n - 1 ]) { return 0 ; } queue < pair < int , int >> q ; int dist [ n ][ n ]; memset ( dist , 0x3f , sizeof ( dist )); for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( grid [ i ][ j ]) { dist [ i ][ j ] = 0 ; q . emplace ( i , j ); } } } int dirs [ 5 ] = { - 1 , 0 , 1 , 0 , - 1 }; while ( ! q . empty ()) { auto [ i , j ] = q . front (); q . pop (); for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < n && y >= 0 && y < n && dist [ x ][ y ] == 0x3f3f3f3f ) { dist [ x ][ y ] = dist [ i ][ j ] + 1 ; q . emplace ( x , y ); } } } vector < tuple < int , int , int >> t ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { t . emplace_back ( dist [ i ][ j ], i , j ); } } sort ( t . begin (), t . end ()); reverse ( t . begin (), t . end ()); UnionFind uf ( n * n ); for ( auto [ d , i , j ] : t ) { for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < n && y >= 0 && y < n && dist [ x ][ y ] >= d ) { uf . unite ( i * n + j , x * n + y ); } } if ( uf . find ( 0 ) == uf . find ( n * n - 1 )) { return d ; } } return 0 ; } };
```

### Python

```python
class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . size = [ 1 ] * n def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa == pb : return False if self . size [ pa ] > self . size [ pb ]: self . p [ pb ] = pa self . size [ pa ] += self . size [ pb ] else : self . p [ pa ] = pb self . size [ pb ] += self . size [ pa ] return True class Solution : def maximumSafenessFactor ( self , grid : List [ List [ int ]]) -> int : n = len ( grid ) if grid [ 0 ][ 0 ] or grid [ n - 1 ][ n - 1 ]: return 0 q = deque () dist = [[ inf ] * n for _ in range ( n )] for i in range ( n ): for j in range ( n ): if grid [ i ][ j ]: q . append (( i , j )) dist [ i ][ j ] = 0 dirs = ( - 1 , 0 , 1 , 0 , - 1 ) while q : i , j = q . popleft () for a , b in pairwise ( dirs ): x , y = i + a , j + b if 0 <= x < n and 0 <= y < n and dist [ x ][ y ] == inf : dist [ x ][ y ] = dist [ i ][ j ] + 1 q . append (( x , y )) q = (( dist [ i ][ j ], i , j ) for i in range ( n ) for j in range ( n )) q = sorted ( q , reverse = True ) uf = UnionFind ( n * n ) for d , i , j in q : for a , b in pairwise ( dirs ): x , y = i + a , j + b if 0 <= x < n and 0 <= y < n and dist [ x ][ y ] >= d : uf . union ( i * n + j , x * n + y ) if uf . find ( 0 ) == uf . find ( n * n - 1 ): return int ( d ) return 0
```