Problem Statement in English

You’re given a 2D grid of integers, where each cell represents the health cost to step on that cell.

You start at the top-left corner of the grid and want to reach the bottom-right corner.

Each cell is either safe (0) or has a thief (1). You want to find the path from the top-left to the bottom-right that maximizes the minimum distance to any thief.

Return the maximum safeness factor of a path from the top-left to the bottom-right corner of the grid. The safeness factor of a path is defined as the minimum distance to any thief along that path.

Approach

There’s 2 parts to this problem:

  1. Find the nearest thief to a cell.
  2. Find the path with the maximum safeness factor.

For part 1, we can use a mutli source breadth first search starting from all the thief cells (cells with value 1) and calculate the minimum distance to any thief for each cell in the grid.

For part 2, we can use a max heap to explore the cells in order of their safeness factor. We start from the top-left corner and explore the neighboring cells, always choosing the cell with the highest safeness factor. We continue this process until we reach the bottom-right corner.

And we’re done!

Solution in Python


class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        
        mmd = [[inf] * N for _ in range(M)]
        queue = deque()
        
        for i in range(M):
            for j in range(N):
                if grid[i][j] == 1:
                    mmd[i][j] = 0
                    queue.append((i, j))
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < M and 0 <= nc < N and mmd[nr][nc] == inf:
                    mmd[nr][nc] = mmd[r][c] + 1
                    queue.append((nr, nc))
                    
        heap = [(-mmd[0][0], 0, 0)]
        seen = set()
        
        while heap:
            s, x, y = heappop(heap)
            s *= -1
            
            if x == M - 1 and y == N - 1: 
                return s
                
            if (x, y) in seen: 
                continue
            seen.add((x, y))
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < M and 0 <= ny < N and (nx, ny) not in seen:
                    ns = min(s, mmd[nx][ny])
                    heappush(heap, (-ns, nx, ny))
                    
        return 0

Complexity

  • Time: $O(MN \log(MN))$
    Since we use a heap to store the cells and explore them in order of their safeness factor.

  • Space: $O(MN)$
    Since we use a heap to store the cells and a set to keep track of visited cells.

Mistakes I Made

I tried to brute force the minimum manhattan distance for each cell to the nearest thief, but that would take $O(M^2N^2)$ time. Instead, I used a BFS to calculate the minimum manhattan distance for each cell in $O(MN)$ time.

And we are done.