LeetCode 2812 - Find the Safest Path in a Grid

This problem asks us to find a path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1) that maximizes its safeness factor. The grid contains thieves, represented by cells with value 1, and empty cells, represented by 0.

leetcodemediumarraybinary-searchbreadth-first-searchunion-findheap-(priority-queue)matrix

LeetCode Problem 2812

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix

Solution

LeetCode 2812 - Find the Safest Path in a Grid

Problem Understanding

This problem asks us to find a path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1) that maximizes its safeness factor.

The grid contains thieves, represented by cells with value 1, and empty cells, represented by 0. We are allowed to move in the four cardinal directions and may even walk through thief cells if necessary.

The key concept is the safeness factor of a path. For every cell on a path, we compute its Manhattan distance to the nearest thief. Among all cells on that path, we take the minimum of those distances. That minimum value is the safeness factor of the path.

Our goal is to find the path whose minimum distance-to-thief value is as large as possible.

Another way to think about the problem is:

  • Every cell has a "safety score", equal to its distance from the nearest thief.
  • A path's score is the minimum safety score among all cells on that path.
  • We want the path whose minimum safety score is maximized.

The constraints are important:

  • n ≤ 400
  • Total cells = n² ≤ 160,000

This is far too large for any solution that repeatedly explores all possible paths. We need an algorithm that runs close to linear or O(n² log n²).

There is also a guarantee that at least one thief exists somewhere in the grid, so every cell has a well-defined distance to a thief.

Important Edge Cases

A thief may be located at (0,0) or (n-1,n-1). In that case, every path must include a thief cell, making the answer 0.

The grid may contain many thieves, causing large portions of the grid to have very small safety values.

The optimal path is not necessarily the shortest path. A longer route may avoid dangerous areas and achieve a larger safeness factor.

A naive implementation might repeatedly compute distances to thieves, which becomes prohibitively expensive when there are up to 160,000 cells.

Approaches

Brute Force

A brute-force approach would enumerate all possible paths from the start to the destination.

For each path, we would determine the distance from every visited cell to the nearest thief and compute the minimum of those distances. The maximum among all path safeness factors would be the answer.

This approach is correct because it directly evaluates every possible path and chooses the best one.

Unfortunately, the number of paths grows exponentially with the grid size. Even for relatively small grids, exhaustive search becomes impossible.

Another slightly less naive version would first compute every cell's distance to the nearest thief and then try all paths using DFS. This still suffers from exponential path exploration.

Key Insight

The problem naturally separates into two phases.

First, compute the distance from every cell to its nearest thief.

This can be done efficiently using multi-source BFS. All thief cells are inserted into the BFS queue initially with distance 0. The BFS wave expands outward and computes the nearest-thief distance for every cell.

After this preprocessing, every cell has a safety value.

Now the problem becomes:

Find a path from start to end that maximizes the minimum cell value along the path.

This is a classic maximum bottleneck path problem.

If we know a candidate safeness factor k, we can ask:

Is there a path from start to finish using only cells whose safety value is at least k?

This question can be answered with a simple BFS.

Since larger values are harder to satisfy than smaller values, the feasibility function is monotonic.

Therefore, we can binary search the answer.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates all possible paths
Optimal O(n² log n) O(n²) Multi-source BFS + binary search + BFS feasibility check

Algorithm Walkthrough

Step 1: Compute nearest-thief distances

Initialize a queue with all thief cells.

Set the distance of every thief cell to 0.

Run a multi-source BFS. Whenever we visit a neighboring cell for the first time, assign it distance current_distance + 1.

When BFS finishes, every cell contains its Manhattan distance to the nearest thief.

Step 2: Determine the binary search range

The minimum possible safeness factor is 0.

The maximum possible safeness factor cannot exceed the largest value in the distance matrix.

Use these values as the binary search boundaries.

Step 3: Create a feasibility test

Given a candidate safeness factor k, determine whether a valid path exists.

First check whether:

  • dist[0][0] >= k
  • dist[n-1][n-1] >= k

If either fails, the answer is immediately false.

Otherwise, run a BFS from (0,0).

Only move into neighboring cells whose distance value is at least k.

If the destination is reached, return true.

Otherwise return false.

Step 4: Binary search the answer

Maintain:

  • left = 0
  • right = max_distance

For each midpoint:

  1. Compute mid.
  2. Run the feasibility check.
  3. If a path exists, record mid as a candidate answer and search higher values.
  4. Otherwise search lower values.

Step 5: Return the largest feasible value

The binary search eventually finds the greatest safeness factor for which a valid path exists.

Return that value.

Why it works

The multi-source BFS correctly computes the shortest Manhattan distance from every cell to any thief. Therefore each cell's safety value is accurate.

For any candidate value k, a path exists if and only if there is a connected route consisting entirely of cells with safety value at least k.

Because a path feasible for value k is also feasible for every smaller value, the feasibility function is monotonic. Binary search therefore correctly finds the largest feasible value. Combining the accurate safety values with the monotonic feasibility check guarantees that the returned value is the maximum possible safeness factor.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)

        dist = [[-1] * n for _ in range(n)]
        queue = deque()

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    dist[r][c] = 0
                    queue.append((r, c))

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if (
                    0 <= nr < n
                    and 0 <= nc < n
                    and dist[nr][nc] == -1
                ):
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))

        max_dist = max(max(row) for row in dist)

        def can_reach(safeness: int) -> bool:
            if dist[0][0] < safeness or dist[n - 1][n - 1] < safeness:
                return False

            visited = [[False] * n for _ in range(n)]
            visited[0][0] = True

            queue = deque([(0, 0)])

            while queue:
                r, c = queue.popleft()

                if r == n - 1 and c == n - 1:
                    return True

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc

                    if (
                        0 <= nr < n
                        and 0 <= nc < n
                        and not visited[nr][nc]
                        and dist[nr][nc] >= safeness
                    ):
                        visited[nr][nc] = True
                        queue.append((nr, nc))

            return False

        left = 0
        right = max_dist
        answer = 0

        while left <= right:
            mid = (left + right) // 2

            if can_reach(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        return answer

The implementation begins by computing the nearest-thief distance for every cell using multi-source BFS. All thief locations are inserted into the queue simultaneously, causing the BFS layers to expand outward exactly according to Manhattan distance.

After the distance matrix is built, the helper function can_reach() determines whether a path exists using only cells whose safety value is at least the candidate threshold.

The binary search repeatedly invokes this feasibility test. When a threshold is feasible, the algorithm attempts a larger one. When it is infeasible, the algorithm searches lower values. The largest feasible threshold is returned as the final answer.

Go Solution

package main

func maximumSafenessFactor(grid [][]int) int {
	n := len(grid)

	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = -1
		}
	}

	type Cell struct {
		r, c int
	}

	queue := make([]Cell, 0)

	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 1 {
				dist[r][c] = 0
				queue = append(queue, Cell{r, c})
			}
		}
	}

	directions := [][2]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	head := 0
	for head < len(queue) {
		cur := queue[head]
		head++

		for _, d := range directions {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if nr >= 0 && nr < n &&
				nc >= 0 && nc < n &&
				dist[nr][nc] == -1 {

				dist[nr][nc] = dist[cur.r][cur.c] + 1
				queue = append(queue, Cell{nr, nc})
			}
		}
	}

	maxDist := 0
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			if dist[r][c] > maxDist {
				maxDist = dist[r][c]
			}
		}
	}

	canReach := func(safeness int) bool {
		if dist[0][0] < safeness || dist[n-1][n-1] < safeness {
			return false
		}

		visited := make([][]bool, n)
		for i := range visited {
			visited[i] = make([]bool, n)
		}

		q := []Cell{{0, 0}}
		visited[0][0] = true

		head := 0

		for head < len(q) {
			cur := q[head]
			head++

			if cur.r == n-1 && cur.c == n-1 {
				return true
			}

			for _, d := range directions {
				nr := cur.r + d[0]
				nc := cur.c + d[1]

				if nr >= 0 && nr < n &&
					nc >= 0 && nc < n &&
					!visited[nr][nc] &&
					dist[nr][nc] >= safeness {

					visited[nr][nc] = true
					q = append(q, Cell{nr, nc})
				}
			}
		}

		return false
	}

	left := 0
	right := maxDist
	answer := 0

	for left <= right {
		mid := left + (right-left)/2

		if canReach(mid) {
			answer = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return answer
}

The Go version follows exactly the same algorithm. Instead of Python's deque, it uses a slice together with a moving head index, which provides efficient queue behavior without repeatedly removing elements from the front. Integer overflow is not a concern because all distance values are bounded by roughly 2 * (n - 1), which is well within Go's integer range.

Worked Examples

Example 1

grid =
[
 [1,0,0],
 [0,0,0],
 [0,0,1]
]

Distance Matrix

Cell Distance
(0,0) 0
(0,1) 1
(0,2) 2
(1,0) 1
(1,1) 2
(1,2) 1
(2,0) 2
(2,1) 1
(2,2) 0

Resulting matrix:
0 1 2
1 2 1
2 1 0

Start cell safety is 0.

Therefore no path can have safeness greater than 0.

Answer = 0.

Example 2

grid =
[
 [0,0,1],
 [0,0,0],
 [0,0,0]
]

Distance Matrix
2 1 0
3 2 1
4 3 2

Binary search checks:

Candidate Reachable?
2 Yes
3 No

For safeness 2, a valid path exists:

(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)

Visited safety values:

2, 3, 4, 3, 2

Minimum = 2.

Answer = 2.

Example 3

grid =
[
 [0,0,0,1],
 [0,0,0,0],
 [0,0,0,0],
 [1,0,0,0]
]

Distance Matrix
3 2 1 0
2 3 2 1
1 2 3 2
0 1 2 3

Binary search tests:

Candidate Reachable?
1 Yes
2 Yes
3 No

Largest feasible value is 2.

Answer = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n² log n) One multi-source BFS plus O(log n) feasibility BFS checks
Space O(n²) Distance matrix, visited matrix, and BFS queues

The multi-source BFS visits each cell exactly once, requiring O(n²) time. Each feasibility check also visits at most all cells, requiring O(n²) time. The maximum distance in an n × n grid is O(n), so binary search performs O(log n) iterations. Therefore the total complexity is O(n² log n).

Test Cases

sol = Solution()

assert sol.maximumSafenessFactor(
    [[1,0,0],[0,0,0],[0,0,1]]
) == 0  # thieves at both endpoints

assert sol.maximumSafenessFactor(
    [[0,0,1],[0,0,0],[0,0,0]]
) == 2  # sample case 2

assert sol.maximumSafenessFactor(
    [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
) == 2  # sample case 3

assert sol.maximumSafenessFactor(
    [[1]]
) == 0  # single cell thief

assert sol.maximumSafenessFactor(
    [[0,1],[0,0]]
) == 1  # small grid

assert sol.maximumSafenessFactor(
    [[0,0],[0,1]]
) == 0  # destination is thief

assert sol.maximumSafenessFactor(
    [[1,0],[0,0]]
) == 0  # start is thief

assert sol.maximumSafenessFactor(
    [[0,0,0],
     [0,1,0],
     [0,0,0]]
) == 1  # central thief

assert sol.maximumSafenessFactor(
    [[0,0,0,0],
     [0,0,0,0],
     [0,0,0,0],
     [1,0,0,0]]
) == 0  # start area constrained by bottom thief

assert sol.maximumSafenessFactor(
    [[0,0,1,0],
     [0,0,0,0],
     [1,0,0,0],
     [0,0,0,0]]
) >= 0  # multiple thieves

Test Summary

Test Why
[[1,0,0],[0,0,0],[0,0,1]] Thieves at both endpoints
[[0,0,1],[0,0,0],[0,0,0]] Sample case with answer 2
[[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]] Multiple distant thieves
[[1]] Smallest possible grid
[[0,1],[0,0]] Small grid with nearby thief
[[0,0],[0,1]] Destination cell is a thief
[[1,0],[0,0]] Starting cell is a thief
[[0,0,0],[0,1,0],[0,0,0]] Symmetric central thief
Large open grid with one thief Distance propagation validation
Multiple thief configuration General stress coverage

Edge Cases

Start Cell Contains a Thief

If grid[0][0] == 1, then the path begins on a thief cell. Since the distance from that cell to the nearest thief is zero, every path has a minimum safety value of at most zero. A common bug is forgetting that the starting cell itself contributes to the path safeness factor. The implementation handles this naturally because the BFS distance matrix assigns distance 0 to thief cells.

Destination Cell Contains a Thief

If grid[n-1][n-1] == 1, every valid path must end on a thief cell. Therefore the safeness factor cannot exceed zero. The binary search feasibility check correctly rejects any threshold larger than zero because the destination distance value is zero.

Large Regions with Multiple Thieves

When many thieves are scattered throughout the grid, a cell may be close to several thieves simultaneously. Computing distances independently from every thief would be extremely expensive. The multi-source BFS solves this by expanding from all thieves at once, guaranteeing that the first time a cell is reached, its shortest distance to any thief has been found.

Single Cell Grid

For a 1 × 1 grid containing a thief, the answer is immediately zero. This corner case often breaks path-finding implementations because the start and destination are the same cell. The algorithm handles it correctly because the BFS distance matrix assigns the cell distance zero, and the binary search returns zero as the largest feasible value.

Optimal Path Is Not the Shortest Path

A shortest route may pass near thieves and therefore have a low safeness factor. A longer route can sometimes maintain a larger minimum distance from thieves and produce a better answer. The algorithm does not optimize path length. Instead, it checks whether a threshold can be maintained throughout an entire path, which directly matches the problem's objective.