2812. Medium

Find the Safest Path in a Grid🔗

MediumArrayBreadth-First SearchHeap (Priority Queue)

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:

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.

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.

Bruteforce Approach — DFS on all paths

O(4^(n²)) Time

🐢

Exhaustive Search (TLE)

The most naive way to solve this is to explore every possible path from (0,0) to (n-1,n-1) using Depth-First Search (DFS).

1For every cell you visit on a path, you would need to calculate its distance to all thieves to find the minimum distance for that cell.
2Then, you would take the minimum of these distances for all cells along the path to get the path's safeness factor.
3Finally, you maximize this value across all valid paths to the destination.

Why we don't do this (and why we use BFS instead): Computing the distance to all thieves for every single cell is extremely redundant and slow. Additionally, there are exponentially many paths in a grid. By using Multi-Source BFS, we can precalculate the minimum distance to the nearest thief for every cell globally in just O(n²) time. Then, Dijkstra allows us to greedily pick the safest route without exhaustively exploring all paths!

Optimal Approach — Multi-Source BFS + Dijkstra's Algorithm

O(n² log n) Time

🔍

Maximizing the Minimum (Path Safeness)

Time O(n² log n)Space O(n²)

The problem asks us to find a path where the minimum distance to a thief is maximized. This is a classic "maximize the minimum" path problem.

1Multi-Source BFS: First, we need to know the distance from every cell to the nearest thief. We start a BFS from all thieves simultaneously. This gives us the minDist for every cell in O(n²) time.
2Dijkstra with Max-Heap: Next, we use Dijkstra's Algorithm to find the safest path. Instead of a min-heap, we use a Max-Heap to always process the path that has the highest current safeness factor.
3As we expand to neighbors, the safeness of the path to that neighbor becomes min(current_safeness, minDist[neighbor]).
4When we pop the destination cell (n-1, n-1) from the Max-Heap, we are guaranteed to have found the path with the maximum possible safeness factor!

READYPress ▶ or step forward to begin.

✓

—

Grid (JSON Format)

Executing Code

class Solution:

    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:

        N = len(grid)

        # 1. Multi-source BFS to find min dist to thief

        q = deque()

        min_dist = [[-1] * N for _ in range(N)]

        for r in range(N):

            for c in range(N):

                if grid[r][c] == 1:

                    q.append((r, c))

                    min_dist[r][c] = 0

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

        while q:

            r, c = q.popleft()

            for dr, dc in dirs:

                r2, c2 = r + dr, c + dc

                if 0 <= r2 < N and 0 <= c2 < N and min_dist[r2][c2] == -1:

                    min_dist[r2][c2] = min_dist[r][c] + 1

                    q.append((r2, c2))

        # 2. Dijkstra with Max-Heap for the safest path

        maxHeap = [(-min_dist[0][0], 0, 0)]

        safe_factor = [[-1] * N for _ in range(N)]

        safe_factor[0][0] = min_dist[0][0]

        while maxHeap:

            dist, r, c = heapq.heappop(maxHeap)

            dist = -dist

            if (r, c) == (N-1, N-1):

                return dist

            for dr, dc in dirs:

                r2, c2 = r + dr, c + dc

                if 0 <= r2 < N and 0 <= c2 < N:

                    dist2 = min(dist, min_dist[r2][c2])

                    if dist2 > safe_factor[r2][c2]:

                        safe_factor[r2][c2] = dist2

                        heapq.heappush(maxHeap, (-dist2, r2, c2))

        return 0

Discussion

…

Loading comments…

LeetMotion