2812. Find the Safest Path in a Grid LeetCode Solution
In this guide, you will get 2812. Find the Safest Path in a Grid LeetCode Solution with the best time and space complexity. The solution to Find the Safest Path in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Safest Path in a Grid
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.
Example 1:
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:
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.
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.
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.
Complexity Analysis
Time Complexity: O(n^2\log n)
Space Complexity: O(n^2)
2812. Find the Safest Path in a Grid LeetCode Solution in C++
class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
const vector<vector<int>> distToThief = getDistToThief(grid);
int l = 0;
int r = grid.size() * 2;
while (l < r) {
const int m = (l + r) / 2;
if (hasValidPath(distToThief, m))
l = m + 1;
else
r = m;
}
return l - 1;
}
private:
static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool hasValidPath(const vector<vector<int>>& distToThief, int safeness) {
if (distToThief[0][0] < safeness)
return false;
const int n = distToThief.size();
queue<pair<int, int>> q{{{0, 0}}};
vector<vector<bool>> seen(n, vector<bool>(n));
seen[0][0] = true;
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
if (distToThief[i][j] < safeness)
continue;
if (i == n - 1 && j == n - 1)
return true;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
return false;
}
vector<vector<int>> getDistToThief(const vector<vector<int>>& grid) {
const int n = grid.size();
vector<vector<int>> distToThief(n, vector<int>(n));
queue<pair<int, int>> q;
vector<vector<bool>> seen(n, vector<bool>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) {
q.emplace(i, j);
seen[i][j] = true;
}
for (int dist = 0; !q.empty(); ++dist) {
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
distToThief[i][j] = dist;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
}
return distToThief;
}
}; /* code provided by PROGIEZ */
2812. Find the Safest Path in a Grid LeetCode Solution in Java
class Solution {
public int maximumSafenessFactor(List<List<Integer>> grid) {
int[][] distToThief = getDistToThief(grid);
int l = 0;
int r = grid.size() * 2;
while (l < r) {
final int m = (l + r) / 2;
if (hasValidPath(distToThief, m))
l = m + 1;
else
r = m;
}
return l - 1;
}
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private boolean hasValidPath(int[][] distToThief, int safeness) {
if (distToThief[0][0] < safeness)
return false;
final int n = distToThief.length;
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(0, 0)));
boolean[][] seen = new boolean[n][n];
seen[0][0] = true;
while (!q.isEmpty()) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
if (distToThief[i][j] < safeness)
continue;
if (i == n - 1 && j == n - 1)
return true;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
q.offer(new Pair<>(x, y));
seen[x][y] = true;
}
}
return false;
}
private int[][] getDistToThief(List<List<Integer>> grid) {
final int n = grid.size();
int[][] distToThief = new int[n][n];
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();
boolean[][] seen = new boolean[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (grid.get(i).get(j) == 1) {
q.offer(new Pair<>(i, j));
seen[i][j] = true;
}
for (int dist = 0; !q.isEmpty(); ++dist) {
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
distToThief[i][j] = dist;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
q.offer(new Pair<>(x, y));
seen[x][y] = true;
}
}
}
return distToThief;
}
} // code provided by PROGIEZ
2812. Find the Safest Path in a Grid LeetCode Solution in Python
class Solution:
def maximumSafenessFactor(self, grid: list[list[int]]) -> int:
self.dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
n = len(grid)
distToThief = self._getDistToThief(grid)
def hasValidPath(safeness: int) -> bool:
if distToThief[0][0] < safeness:
return False
q = collections.deque([(0, 0)])
seen = {(0, 0)}
while q:
i, j = q.popleft()
if distToThief[i][j] < safeness:
continue
if i == n - 1 and j == n - 1:
return True
for dx, dy in self.dirs:
x = i + dx
y = j + dy
if x < 0 or x == n or y < 0 or y == n:
continue
if (x, y) in seen:
continue
q.append((x, y))
seen.add((x, y))
return False
return bisect.bisect_left(range(n * 2), True,
key=lambda m: not hasValidPath(m)) - 1
def _getDistToThief(self, grid: list[list[int]]) -> list[list[int]]:
n = len(grid)
distToThief = [[0] * n for _ in range(n)]
q = collections.deque()
seen = set()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.append((i, j))
seen.add((i, j))
dist = 0
while q:
for _ in range(len(q)):
i, j = q.popleft()
distToThief[i][j] = dist
for dx, dy in self.dirs:
x = i + dx
y = j + dy
if x < 0 or x == n or y < 0 or y == n:
continue
if (x, y) in seen:
continue
q.append((x, y))
seen.add((x, y))
dist += 1
return distToThief # code by PROGIEZ
