2812. Find the Safest Path in a Grid
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.
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.
In a binary min heap, the minimum element can be found in:
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.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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:
1[0, T, 0] 2[T, 0, 0] 3[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[1, T, 1] 2[T, 1, 2] 3[2, 2, 3] -
For the thief at
(1, 0), the grid distances update:1[1, 1, 2] 2[T, 1, 2] 3[1, 2, 3]
The combined result of both gives us the following safeness values grid (minimum distances from the thieves):
1[1, T, 1] 2[T, 1, 2] 3[1, 2, 3] -
-
Sorting by Safeness: We take the cells and sort by their safeness values in descending order:
1[(2, 2), 3] 2[(1, 2), 2] 3[(2, 1), 2] 4[(0, 0), 1] 5[(0, 2), 1] 6[(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:
1(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.
- Cell
-
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. - Cell
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:
1Start -> (0, 0) 2 (0, 2) 3 (1, 2) 4 (2, 1) 5End -> (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.
811class 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}
1061#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};
1121// 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}
99Which of the following shows the order of node visit in a Breadth-first Search?
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
distarray has a time complexity ofO(n^2)since each cell in then x ngrid is processed at most once. - Sorting the distances has a time complexity of
O(n^2 * log (n^2))which simplifies toO(n^2 * log n)because we are sortingn^2elements. - 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 mostn^2union operations, this portion of the algorithm also has a time complexity ofO(n^2 * log n).
Space Complexity
The space complexity of the algorithm is O(n^2) for the following data structures:
- The
distarray which holds distance values for each grid cell requiresO(n^2)space. - The
UnionFindclass uses two arrays (pandsize), each ofn^2elements, which collectively requireO(n^2)space. - The queue
q, in the worst case, could hold all the cells of the grid, requiringO(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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.