#2812

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find the Safest Path in a Grid

Find the Safest Path in a Grid uses binary search and BFS to maximize path safeness from thieves in a grid.

array binary search breadth first search union find heap priority queue

Problem Statement

You are given a 0-indexed 2D matrix grid of size n x n, where each cell is either 0 (empty) or 1 (contains a thief). Starting from the top-left corner (0, 0), your task is to find the safest path to the bottom-right corner (n-1, n-1). In each move, you can travel to any adjacent cell, including those containing thieves. The objective is to determine the maximum safeness factor for any valid path.

The safeness factor of a path is defined as the minimum Manhattan distance from any cell in the path to any thief. You are to compute the maximum safeness factor achievable for a valid path from the top-left to the bottom-right corner of the grid, while considering obstacles such as thieves.

Examples

Example 1

Input: grid = [[1,0,0],[0,0,0],[0,0,1]]

Output: 0

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

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

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.

Solution Approach

Binary Search Over Safeness Factor

The core of the solution uses binary search over possible safeness factors, from 0 to n. This approach works because we can narrow down the range of safeness by testing each candidate value, reducing the complexity of brute-forcing all possible paths.

Breadth-First Search (BFS) to Validate Paths

For each candidate safeness factor from the binary search, we use BFS to check whether there exists a valid path where all points have at least that safeness factor. BFS ensures that we efficiently explore the grid from the top-left to bottom-right corners while adhering to the safeness constraint.

Combining Binary Search and BFS

By combining binary search with BFS, we balance efficiency and correctness. Binary search reduces the number of possible safeness factors to check, while BFS ensures that we find a valid path for each safeness level tested. This combination optimizes the overall solution.

Complexity Analysis

Metric	Value
Time	O(n^2 \cdot \log (n))
Space	O(n^2)

The time complexity is O(n^2 * log(n)) because for each of the O(log(n)) iterations of binary search, we perform an O(n^2) BFS to check if a path with the given safeness factor exists. The space complexity is O(n^2) due to the grid and BFS queue.

What Interviewers Usually Probe

Candidate effectively applies binary search over a range of potential safeness factors.
Candidate demonstrates clear understanding of BFS for pathfinding in a grid with constraints.
Candidate explains the trade-offs in combining binary search and BFS to optimize the solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the thieves in the grid when calculating safeness factor.
Misunderstanding the binary search range, which may lead to incorrect results.
Not efficiently handling the BFS queue, leading to performance issues for larger grids.

Follow-up variants

Handling grids with varying thief positions and grid sizes.
Modifying the problem to account for multiple thieves instead of a single thief.
Changing the grid shape, such as making it non-square, and adjusting the approach.

FAQ

How do I approach the 'Find the Safest Path in a Grid' problem?

The problem can be solved efficiently using a combination of binary search over safeness factors and BFS to validate paths at each safeness level.

What is the primary pattern in the 'Find the Safest Path in a Grid' problem?

The primary pattern is binary search over the valid answer space, combined with BFS for path validation at each candidate safeness factor.

What is the time complexity of the solution?

The time complexity is O(n^2 * log(n)), where n is the grid size. The binary search performs O(log(n)) checks, each requiring an O(n^2) BFS.

Can BFS alone solve the problem?

BFS alone isn't enough because we need to search over different safeness factors, which is why binary search is needed to optimize the solution.

What are the key trade-offs when using binary search and BFS together?

The main trade-off is balancing the efficiency of binary search with the correctness of BFS. While binary search reduces the number of possible safeness levels to check, BFS ensures each path is validated against the safeness constraint.

terminal

Solution

Solution 1: BFS + Sorting + Union-Find

We can first find out the positions of all thieves, and then start multi-source BFS from these positions to get the shortest distance from each position to the thieves. Then sort in descending order according to the distance, and add each position to the union-find set one by one. If the start and end points are in the same connected component, the current distance is the answer.

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

Solution 2

#### TypeScript

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

Continue Practicing

#1631 path with minimum effort #2617 minimum number of visited cells in a grid #2503 maximum number of points from grid queries