2812. Find the Safest Path in a Grid

MediumBreadth-First SearchUnion FindArrayBinary SearchMatrix

Problem Description

This problem involves finding a path in a grid matrix from the top-left corner to the bottom-right corner, which avoids thieves as much as possible. In the matrix:

A cell with a value of 1 indicates that there is a thief.
A cell with a value of 0 is an empty cell that you can move through.

From your starting position at cell (0, 0), you can move horizontally or vertically to adjacent cells until you reach the cell (n - 1, n - 1) at the opposite corner of the grid. The goal is to find a path with the highest safeness factor, which is measured as the smallest Manhattan distance from any thief along your path. Remember that the Manhattan distance between two points (a, b) and (x, y) is equal to the absolute value of the differences of their coordinates, |a - x| + |b - y|. You need to figure out the best path that maximizes the minimum distance to the nearest thief at any point along the path.

Flowchart Walkthrough

To solve LeetCode 2812. Find the Safest Path in a Grid, let's follow the decision-making process using the Flowchart. Here's a step-by-step approach according to the provided nodes and edges in the flowchart:

Is it a graph?

Yes: The grid can be considered a graph where each cell represents a node connected to its immediately adjacent neighbors (up, down, left, right).

Is it a tree?

No: There could be multiple possible paths from one cell to another without any hierarchical parent-child relationships, so it's not a tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

No: The problem deals with grids, and though they contain directed paths, they are not inherently acyclic because the context is about safety in paths, not graph directionality or ordering.

Is the problem related to shortest paths?

Yes: The challenge involves finding not just any path but the safest (likely optimal in some sense, like least dangerous) path from a starting position to a goal.

Is the graph weighted?

Yes: If we interpret 'safest' as a function of path weights, where each cell has a risk or weight denoting safety, then we can treat the grid as a weighted graph where each edge weight signifies the risk involved walking from one cell to its neighbor.

Conclusion: Given that the problem involves finding a shortest path in a weighted graph, using Breadth-First Search (BFS) is suitable, particularly its adaptation, Dijkstra's Algorithm, helps in efficiently exploring all the possible paths while prioritizing those with lower cumulative weights (i.e., safer). Hence, BFS, adapted to handle weights via priority queues, is the prescribed algorithm for finding the safest path in the grid.

Therefore, this analysis tips the BFS approach, especially useful for navigating weighted grids and ensuring optimal traversal using the least risky or most safe path values.

Intuition

The solution strategy involves several steps:

Use a breadth-first search (BFS) to find the distance of all cells from the nearest thief. This step involves all thieves in the grid functioning as sources for the BFS, thus computing the shortest distance from each cell to any thief. The result is the minimum distance for each cell to a thief, which indirectly represents the safeness when passing through that cell.
Once all distances are calculated, sort all the cells by their safeness factor in descending order. By doing this, we know the potential safeness factors we can achieve.
After sorting, we use a Union-Find data structure to find out whether it is possible to travel from the start to the end while maintaining at least a certain safeness factor throughout the path. We start with the safest (highest distance) cells and progressively include less safe cells. Each time we add a cell, we perform union operations to connect the cell with its adjacent cells in the Union-Find structure if they have an equal or higher safeness factor.
The process continues until cell (0, 0) and cell (n - 1, n - 1) are in the same connected component in the Union-Find structure. At this point, the current distance value being considered is the maximum safeness factor for a valid path from start to end because it is the lowest distance to a thief that is common across the entire path.

In summary, the intuition behind this solution is to map out the danger levels throughout the grid using BFS, then try to navigate the grid from the safest spots to the riskiest, ensuring connectivity from start to finish, which is facilitated by the Union-Find structure.

Learn more about Breadth-First Search, Union Find and Binary Search patterns.

Solution Approach

The implementation begins with setting up a BFS to determine the minimum distance from each cell to the nearest thief. This is necessary to ascertain the potential safeness of each point on the grid. We use a queue q to manage the BFS process. Cells containing thieves are enqueued first with a distance of zero. The grid is traversed, and for each cell, we check its neighbors. If a neighbor has not been visited (indicated by a distance of infinity inf), we set its distance as one more than the current and enqueue it.

The cells' coordinates and their associated distances are then sorted. This sorting is in descending order based on distances since we are interested in maintaining the highest possible safeness factor as we build our path from (0, 0) to (n - 1, n - 1).

Next, we use a Union-Find structure to help us assess connectivity across the grid while maintaining a high safeness factor. We iterate over the sorted list, and for each cell, we try to union it with its neighbors if they have equal or greater safeness factors (distances from thieves).

Union-Find is a data structure that keeps track of elements that are split into one or more disjoint sets. It supports two main operations: find, which returns the representative element (or the "root") of the set that an element belongs to, and union, which merges the sets that contain two elements.

The union operation is used both to merge cells into larger safe zones and to check whether the start and end cells become connected. Once (0, 0) and (n - 1, n - 1) are combined into the same set, we have found a path with the maximum possible safeness factor, because any further inclusion of cells will either maintain or decrease the safeness factor of the path.

The while condition checks for the connectivity between the start and end by comparing the root of their sets. If they match, it means there is a path between them with the current safeness factor since all involved cells have safely united under this condition.

If a path is established, the minimum distance common to the entire path (the safeness factor) is returned. The logic enforces that the path we construct respects the highest minimum distance to any thief along the way, maximizing the safety factor. If no such path is possible, for example, if either the start or the end cell contains a thief, the function returns zero, indicating no safe path exists.

By using a combination of BFS for safety distance computations, sorting for path prioritization, and Union-Find for dynamic region connectivity, we create an efficient algorithm to solve this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using a 3x3 grid. Consider the following grid where T represents a thief:

[0, T, 0]
[T, 0, 0]
[0, 0, 0]

Breadth-First Search (BFS): We initiate BFS from all the thief's locations:
- For the cell with the thief at (0, 1), we have grid updated with distances:
```
[1, T, 1]
[T, 1, 2]
[2, 2, 3]
```
- For the thief at (1, 0), the grid distances update:
```
[1, 1, 2]
[T, 1, 2]
[1, 2, 3]
```
The combined result of both gives us the following safeness values grid (minimum distances from the thieves):
```
[1, T, 1]
[T, 1, 2]
[1, 2, 3]
```

Sorting by Safeness: We take the cells and sort by their safeness values in descending order:

[(2, 2), 3]
[(1, 2), 2]
[(2, 1), 2]
[(0, 0), 1]
[(0, 2), 1]
[(2, 0), 1]

Union-Find Structure: Now we use a Union-Find data structure starting from the cell with the highest safeness value. The initial sets for each cell will be:
```
(0, 0), (0, 2), (1, 2), (2, 1), (2, 0), (2, 2)
```
Then we apply the union for each one, considering the safeness factors (only combining with neighbors of equal or greater safeness):
- Cell (2, 2) with safeness 3 joins with (2, 1) and (1, 2) having safeness 2 or more.
- Cell (1, 2) connects with (0, 2).
At this point, our sets reflect that we can start building paths from lower-right towards the start while ensuring safety.
Finding the Path: Continuing the union operations and checking for connectivity, we look at:
- Cell (0, 0) can only join with (0, 2) since they share the same safeness factor of 1.
After the above unions, the sets would look like this:
- {(2, 2), (2, 1), (1, 2), (0, 2), (0, 0)}, {(2, 0)}
We establish that (0, 0) is connected to (2, 2) with a safeness factor of 1, which is the maximum safeness we can assure across all the path due to the initial position being 1 step away from a thief.

So the maximum safeness factor for a path from the top-left corner to the bottom-right corner in this grid is 1, and a valid path respecting this factor might look something like this:

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

This visualization breaks down how we can use BFS for danger-level mapping, sorting for path strategy, and Union-Find for connectivity to find the safest path across a grid with thieves, hence solving the given problem.

Solution Implementation

1from collections import deque
2from itertools import pairwise
3from typing import List
4
5class UnionFind:
6    """A class that implements the Union-Find (Disjoint Set) data structure."""
7  
8    def __init__(self, size):
9        # Parent pointers initialised to point to themselves and sizes initialised to 1
10        self.parent = list(range(size))
11        self.set_size = [1] * size
12
13    def find(self, x):
14        """Finds the representative (root) of the set containing 'x'. Implements path compression."""
15        if self.parent[x] != x:
16            self.parent[x] = self.find(self.parent[x])
17        return self.parent[x]
18
19    def union(self, a, b):
20        """Unites the sets containing 'a' and 'b'. Return False if they are already in the same set, True otherwise."""
21        root_a, root_b = self.find(a), self.find(b)
22        if root_a == root_b:
23            return False
24          
25        # Union by size, making the smaller root point to the larger one
26        if self.set_size[root_a] > self.set_size[root_b]:
27            self.parent[root_b] = root_a
28            self.set_size[root_a] += self.set_size[root_b]
29        else:
30            self.parent[root_a] = root_b
31            self.set_size[root_b] += self.set_size[root_a]
32        return True
33
34
35class Solution:
36    def maximum_safeness_factor(self, grid: List[List[int]]) -> int:
37        """Calculates the maximum safeness factor in a grid avoiding unsafe cells."""
38        # Initialize variables
39        n = len(grid)
40        # If start or end cells are unsafe, return 0
41        if grid[0][0] or grid[n - 1][n - 1]:
42            return 0
43          
44        # BFS to find distances from unsafe cells
45        queue = deque()
46        dist = [[float('inf')] * n for _ in range(n)]
47        # Seed initial distances for unsafe cells
48        for i in range(n):
49            for j in range(n):
50                if grid[i][j]:
51                    queue.append((i, j))
52                    dist[i][j] = 0
53        # Directions for moving to adjacent cells
54        directions = (-1, 0, 1, 0, -1)
55        while queue:
56            ci, cj = queue.popleft()
57            for da, db in pairwise(directions):
58                ni, nj = ci + da, cj + db
59                if 0 <= ni < n and 0 <= nj < n and dist[ni][nj] == float('inf'):
60                    dist[ni][nj] = dist[ci][cj] + 1
61                    queue.append((ni, nj))
62
63        # Sort cells based on their distance from unsafe cells in descending order
64        candidates = sorted(((dist[i][j], i, j) for i in range(n) for j in range(n)), reverse=True)
65        uf = UnionFind(n * n)
66        for d, i, j in candidates:
67            # Attempt to connect current cell with all its neighbors
68            for da, db in pairwise(directions):
69                x, y = i + da, j + db
70                if 0 <= x < n and 0 <= y < n and dist[x][y] >= d:
71                    uf.union(i * n + j, x * n + y)
72            # Check if start and end cells are connected
73            if uf.find(0) == uf.find(n * n - 1):
74                return int(d)
75        return 0
76
77# Example usage:
78# sol = Solution()
79# result = sol.maximum_safeness_factor([[0, 1], [1, 0]])
80# print(result)  # Output depends on the grid configuration.
81

1class Solution {
2    public int maximumSafenessFactor(List<List<Integer>> grid) {
3        int n = grid.size();
4      
5        // Check for obstacles at start or end positions.
6        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
7            return 0; // No path if start or end is blocked.
8        }
9      
10        Deque<int[]> queue = new ArrayDeque<>();
11        int[][] distances = new int[n][n];
12        final int INF = 1 << 30;
13      
14        // Initialize distances to "infinity"
15        for (int[] distanceRow : distances) {
16            Arrays.fill(distanceRow, INF);
17        }
18      
19        // Initial distance for all obstacles set to 0 and added to queue.
20        for (int i = 0; i < n; ++i) {
21            for (int j = 0; j < n; ++j) {
22                if (grid.get(i).get(j) == 1) {
23                    distances[i][j] = 0;
24                    queue.offer(new int[] {i, j});
25                }
26            }
27        }
28      
29        // Directions for up, right, down, left traversal.
30        int[] directionDeltas = {-1, 0, 1, 0, -1};
31      
32        // Perform a multi-source BFS to find shortest distance to obstacles for each cell.
33        while (!queue.isEmpty()) {
34            int[] position = queue.poll();
35            int i = position[0], j = position[1];
36            for (int k = 0; k < 4; ++k) {
37                int x = i + directionDeltas[k], y = j + directionDeltas[k + 1];
38                if (x >= 0 && x < n && y >= 0 && y < n && distances[x][y] == INF) {
39                    distances[x][y] = distances[i][j] + 1;
40                    queue.offer(new int[] {x, y});
41                }
42            }
43        }
44      
45        // Store each cell as [distance, row, column].
46        List<int[]> sortedCellsByDistance = new ArrayList<>();
47        for (int i = 0; i < n; ++i) {
48            for (int j = 0; j < n; ++j) {
49                sortedCellsByDistance.add(new int[] {distances[i][j], i, j});
50            }
51        }
52      
53        // Sort cells by distance in descending order.
54        sortedCellsByDistance.sort((a, b) -> Integer.compare(b[0], a[0]));
55      
56        UnionFind unionFind = new UnionFind(n * n);
57      
58        // Try to connect cells starting with the safest (largest distance).
59        for (int[] cell : sortedCellsByDistance) {
60            int distance = cell[0], i = cell[1], j = cell[2];
61            for (int k = 0; k < 4; ++k) {
62                int x = i + directionDeltas[k], y = j + directionDeltas[k + 1];
63                if (x >= 0 && x < n && y >= 0 && y < n && distances[x][y] >= distance) {
64                    unionFind.union(i * n + j, x * n + y);
65                }
66            }
67            // Check if start is connected to end.
68            if (unionFind.find(0) == unionFind.find(n * n - 1)) {
69                return distance;
70            }
71        }
72        return 0; // If no path is found.
73    }
74}
75
76class UnionFind {
77    private int[] parents;
78    private int count;
79
80    public UnionFind(int totalNodes) {
81        parents = new int[totalNodes];
82        for (int i = 0; i < totalNodes; ++i) {
83            parents[i] = i; // Each node is its own parent at the beginning.
84        }
85        this.count = totalNodes;
86    }
87
88    public boolean union(int a, int b) {
89        int parentA = find(a);
90        int parentB = find(b);
91        if (parentA == parentB) {
92            return false;
93        }
94        parents[parentA] = parentB;
95        --count;
96        return true;
97    }
98
99    public int find(int x) {
100        if (parents[x] != x) {
101            parents[x] = find(parents[x]);
102        }
103        return parents[x];
104    }
105}
106

1#include <vector>
2#include <numeric>
3#include <queue>
4#include <tuple>
5#include <cstring>
6#include <algorithm>
7
8using namespace std;
9
10class UnionFind {
11public:
12    vector<int> parent;
13    int count;
14
15    // Constructor initializes UnionFind with `n` elements
16    UnionFind(int n)
17        : count(n), parent(n) {
18        // Fill the parent vector with indices of itself (self parentage)
19        iota(parent.begin(), parent.end(), 0);
20    }
21
22    // Unite two groups; if they are already united, return false
23    bool unite(int a, int b) {
24        int rootA = find(a), rootB = find(b);
25        if (rootA == rootB) return false;
26        // Assign the parent of A's root to be B's root
27        parent[rootA] = rootB;
28        --count; // Decrease the number of disjoint sets
29        return true;
30    }
31
32    // Find the root of the group that element `x` is in
33    int find(int x) {
34        // Path compression: point this node directly to the root
35        if (parent[x] != x) parent[x] = find(parent[x]);
36        return parent[x];
37    }
38};
39
40class Solution {
41public:
42    // Calculates the maximum safeness factor of a given grid
43    int maximumSafenessFactor(vector<vector<int>>& grid) {
44        int gridSize = grid.size();
45        // If the start or end points are blocked, return 0
46        if (grid[0][0] || grid[gridSize - 1][gridSize - 1]) {
47            return 0;
48        }
49
50        queue<pair<int, int>> q; // Queue for BFS
51        // Initialize distance array with large values
52        int dist[gridSize][gridSize];
53        memset(dist, 0x3f, sizeof(dist));
54
55        // Calculate distances from each hazard in the grid
56        for (int i = 0; i < gridSize; ++i) {
57            for (int j = 0; j < gridSize; ++j) {
58                if (grid[i][j]) {
59                    dist[i][j] = 0; // Hazards have zero distance
60                    q.emplace(i, j); // Add hazards to the queue
61                }
62            }
63        }
64
65        // Directions for neighbors (up, right, down, left)
66        int dirs[5] = {-1, 0, 1, 0, -1};
67
68        // Perform BFS to calculate the distance of each cell from the closest hazard
69        while (!q.empty()) {
70            auto [i, j] = q.front();
71            q.pop();
72            for (int k = 0; k < 4; ++k) {
73                int x = i + dirs[k], y = j + dirs[k + 1];
74                if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && 
75                    dist[x][y] == 0x3f3f3f3f) {
76                    dist[x][y] = dist[i][j] + 1; // Update distance
77                    q.emplace(x, y); // Enqueue the current cell
78                }
79            }
80        }
81
82        // Sort the cells by distance in descending order
83        vector<tuple<int, int, int>> distances;
84        for (int i = 0; i < gridSize; ++i) {
85            for (int j = 0; j < gridSize; ++j) {
86                distances.emplace_back(dist[i][j], i, j);
87            }
88        }
89        sort(distances.begin(), distances.end(), greater<>());
90
91        // UnionFind to keep track of connectivity
92        UnionFind uf(gridSize * gridSize);
93
94        // Try to unite cells, starting from the highest distance from hazards
95        for (auto [distance, i, j] : distances) {
96            for (int k = 0; k < 4; ++k) {
97                int x = i + dirs[k], y = j + dirs[k + 1];
98                if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && dist[x][y] >= distance) {
99                    uf.unite(i * gridSize + j, x * gridSize + y);
100                }
101            }
102            // If the start and end points are connected, return the current distance
103            if (uf.find(0) == uf.find(gridSize * gridSize - 1)) {
104                return distance;
105            }
106        }
107
108        // If no path is found, return 0
109        return 0;
110    }
111};
112

1// Size of the grid
2let size: number = 0;
3// Array to store the parent of each element
4let parent: number[] = [];
5
6// Initializes the array for union-find operations with each element as its own parent
7function initializeUnionFind(n: number): void {
8    size = n;
9    parent = new Array(n * n).fill(0).map((_, index) => index);
10}
11
12// Finds the parent of a given element `x` and applies path compression
13function find(x: number): number {
14    if (parent[x] !== x) {
15        parent[x] = find(parent[x]);
16    }
17    return parent[x];
18}
19
20// Unites two elements `a` and `b`. Returns true if they're connected, false otherwise
21function union(a: number, b: number): boolean {
22    const rootA = find(a);
23    const rootB = find(b);
24    if (rootA !== rootB) {
25        parent[rootA] = rootB;
26        size--;
27        return true;
28    }
29    return false;
30}
31
32// Calculates the maximum safeness factor for a given grid
33function maximumSafenessFactor(grid: number[][]): number {
34    const n = grid.length;
35    // If the starting or ending cell is blocked, return 0
36    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
37        return 0;
38    }
39  
40    // Multi-directions for traversing adjacent cells
41    const directions = [-1, 0, 1, 0, -1]; 
42    // Queue for BFS
43    const queue: number[][] = [];
44    // Distance array with initial distances set to infinity
45    const distance: number[][] = Array(n)
46        .fill(0)
47        .map(() => Array(n).fill(Number.POSITIVE_INFINITY));
48    for (let i = 0; i < n; ++i) {
49        for (let j = 0; j < n; ++j) {
50            if (grid[i][j] === 1) {
51                distance[i][j] = 0;
52                queue.push([i, j]);
53            }
54        }
55    }
56  
57    // BFS to determine the shortest distance to the nearest obstacle for each cell
58    while (queue.length > 0) {
59        const [currentRow, currentColumn] = queue.shift()!;
60        for (let k = 0; k < 4; ++k) {
61            const nextRow = currentRow + directions[k];
62            const nextColumn = currentColumn + directions[k + 1];
63            if (nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n && distance[nextRow][nextColumn] === Number.POSITIVE_INFINITY) {
64                distance[nextRow][nextColumn] = distance[currentRow][currentColumn] + 1;
65                queue.push([nextRow, nextColumn]);
66            }
67        }
68    }
69  
70    // Flattened and sorted list of the grid cells together with their distances
71    const sortedCells: [number, number, number][] = [];
72    for (let i = 0; i < n; ++i) {
73        for (let j = 0; j < n; ++j) {
74            sortedCells.push([distance[i][j], i, j]);
75        }
76    }
77    sortedCells.sort((cell1, cell2) => cell2[0] - cell1[0]);
78  
79    // Initialize union-find structure
80    initializeUnionFind(n);
81  
82    // Connect cells in order of highest distance to lowest
83    for (const [dist, row, column] of sortedCells) {
84        for (let k = 0; k < 4; ++k) {
85            const nextRow = row + directions[k];
86            const nextColumn = column + directions[k + 1];
87            if (nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n && distance[nextRow][nextColumn] >= dist) {
88                union(row * n + column, nextRow * n + nextColumn);
89            }
90        }
91        // If the start and end cells are connected, return the current distance
92        if (find(0) === find(n * n - 1)) {
93            return dist;
94        }
95    }
96    // If no safe path is found, return 0
97    return 0;
98}
99

Time and Space Complexity

Time Complexity

The total time complexity of the algorithm is O(n^2 * log n). This is broken down as follows:

BFS to compute the dist array has a time complexity of O(n^2) since each cell in the n x n grid is processed at most once.
Sorting the distances has a time complexity of O(n^2 * log (n^2)) which simplifies to O(n^2 * log n) because we are sorting n^2 elements.
The union-find operations done during the processing of the sorted distances. In the worst case, a union or find operation can be O(log n) if we are using union by size and path compression heuristics. Since we could be doing at most n^2 union operations, this portion of the algorithm also has a time complexity of O(n^2 * log n).

Space Complexity

The space complexity of the algorithm is O(n^2) for the following data structures:

The dist array which holds distance values for each grid cell requires O(n^2) space.
The UnionFind class uses two arrays (p and size), each of n^2 elements, which collectively require O(n^2) space.
The queue q, in the worst case, could hold all the cells of the grid, requiring O(n^2) space.

The dominant term in both time and space complexity is O(n^2), making the space complexity linear in the number of cells and the time complexity quadratic in the number of cells and logarithmic with respect to the grid size when accounting for the union-find operations.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: