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.

Examples

Example 1:

$$ grid = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

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:

$$ grid = \begin{bmatrix} \colorbox{lightgreen} 0 & 0 & 1 \\ \colorbox{lightgreen}0 & 0 & 0 \\ \colorbox{lightgreen}0 & \colorbox{lightgreen}0 & \colorbox{lightgreen}0 \end{bmatrix} $$

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:

$$ grid = \begin{bmatrix} \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & 0 & 1 \\ 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & 0 \\ 0 & 0 & \colorbox{lightgreen} 0 & 0 \\ 1 & 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 \end{bmatrix} $$

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.

Solution

Method 1 - BFS + Dijkstra

We can use BFS to calculate the safeness factor for each cell in the grid, as BFS goes like a wave wise or level by level. We can create distances matrix for eg. 3 like this:

Once, we have distances matrix, now we have to find path such that it’s as far as possible from thief. For this we can simply choose to go at max distance cell starting from {0,0} using max heap. We can easily see, the nearest distance in this path from thief is 2. So, when adding the value in max heap, we add smallest safeness factor we have encountered so far. Once we have reach our destination, we return the smallest safeness factor.

Algorithm

  1. Check if the start or end cell contains a thief. If so, return 0.
  2. Do, multi-source BFS from the points of thief. We set the distance of all the safe nodes based on that.
  3. Then we use max heap to find path with maximum safe distance. Track visited cells to avoid revisiting.
    • Pop from the heap and check if we have reached destination. If so, return the safeness factor.
    • Otherwise, for each neighbour, calculate the new safeness factor and push it into the heap for unvisited cells.
    • This part is very similar to Dijkstra’s algorithm to find shortest path

Video Explanation

Code

Java
class Solution {
	// left, right, up, down
    private static int[][] DIRS = new int[][]{{0,-1}, {0,1}, {-1,0}, {1,0}};

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

		// no path possible
		if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
			return 0;
		}
		
        int[][] distances = new int[n][n];
		
		// queue containing cell coordinates
		Queue<int[]> queue = new LinkedList<>();
		
		// initialize dist matrix and queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
	                distances[i][j] = 0; // just for clarity
                    queue.offer(new int[]{i, j});
                } else {
	                distances[i][j] = -1;
                }
            }
        }  
     
        // fill the distance matrix       
        while(!queue.isEmpty()){
	        // we don't have to do bfs level by level
	        // as we are already storing scores in dist matrix
	        int[] cell = queue.poll();
	        int r = cell[0], c = cell[1];
	        for (int[] dir: DIRS) {
		        int newR = r + dir[0];
		        int newC = c + dir[1];
		        if (newR < 0 || newR >= n || newC < 0 || newC >= n || distances[newR][newC] != -1) {
			        continue;
		        }
		        distances[newR][newC] = distances[r][c] + 1;
		        queue.offer(new int[] {newR, newC});
		        
	        }
        }
        // maxHeap on distance matrix
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2] - a[2]);
        maxHeap.add(new int[]{0, 0, distances[0][0]});
        Set<String> visited = new HashSet<>();
        visited.add(0 + "--" + 0);

		while (!maxHeap.isEmpty()) {
			int[] cell = maxHeap.poll();
			int r = cell[0], c = cell[1], dist = cell[2];
			if (r == n - 1 && c == n - 1) {
                return dist;
            }
			for (int[] dir: DIRS) {
				int newR = r + dir[0];
		        int newC = c + dir[1];
				String key = newR + "--" + newC;
		        if (newR < 0 || newR >= n || newC < 0 || newC >= n || visited.contains(key)) {
			        continue;
		        }
		        int safeDist = Math.min(dist, distances[newR][newC]);
		        maxHeap.offer(new int[] {newR, newC, safeDist});
		        visited.add(key);
			}
		}
		return -1;
    }    
}

Note, that for visited set, we can reuse the the distances matrix. For adding the row and column as visited, we can just multiply current distances[newR][newC] by -1:

distances[newR][newC] *= -1; // mark this as visited

And instead of using visited.contains(key) we can just check dist[newR][newC] < 0. But using visited set is preferred for clarity of reading the code.

Complexity

  • ⏰ Time complexity: O(n^2 log n^2) - We loop on grid once to fill in queue and initial values in distances matrix - this takes O(n^2). Then we perform multi-source BFS with O(n^2) again. Then we use maxHeap to find the path search, and at a time heap contains n^2 element, and searching those elements take O(n^2)log(n^2) time, which will be O(n^2)
  • 🧺 Space complexity: O(n^2)