Find a Safe Walk Through a Grid
MedPrompt
You are given an m x n binary matrix grid and an integer health.
You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).
You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.
Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.
Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.
Example 1:
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.
Example 2:
Input: grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
Output: false
Explanation:
A minimum of 4 health points is needed to reach the final cell safely.
Example 3:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.
Any path that does not go through the cell (1, 1) is unsafe since your health will drop to 0 when reaching the final cell.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 502 <= m * n1 <= health <= m + ngrid[i][j]is either 0 or 1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a brute-force backtracking algorithm to explore all possible simple paths from the starting cell (0, 0) to the destination (m - 1, n - 1). It uses a recursive Depth-First Search (DFS) strategy. To prevent getting stuck in cycles within a single path, a visited array is maintained for the current exploration path.
Algorithm
- Define a recursive function
findPath(row, col, currentHealth, visited). - The
visitedarray tracks cells in the current path to avoid cycles. - Base Case 1: If
currentHealthis not positive, the path is invalid. Returnfalse. - Base Case 2: If the current cell
(row, col)is the destination, a valid path has been found. Returntrue. - Mark the current cell as visited:
visited[row][col] = true. - Iterate through the 4 neighbors
(nr, nc):- Check if the neighbor is within bounds and not visited.
- Calculate health for the next step:
nextHealth = currentHealth - grid[nr][nc]. - If
nextHealthis positive, make a recursive call:findPath(nr, nc, nextHealth, visited). - If the recursive call returns
true, propagate the result by returningtrue.
- If no neighbor leads to a solution, backtrack by unmarking the cell:
visited[row][col] = false. - Return
false. - The initial call is made from
(0, 0)after calculating the health cost of the starting cell.
Walkthrough
The core idea is to try every possible direction (up, down, left, right) from the current cell. If a move is valid (within grid boundaries, not yet visited in the current path, and leaves health positive), we recursively explore from the new cell. If a recursive call eventually reaches the destination, we've found a solution. If an exploration path hits a dead end (no valid moves) or runs out of health, it backtracks to the previous cell and tries a different direction.
This method is exhaustive and guarantees finding a path if one exists, but its downfall is its performance. The number of possible paths in a grid can be enormous, leading to an exponential number of recursive calls.
class Solution { private int m, n; private int[][] grid; private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public boolean canReach(int[][] grid, int health) { this.m = grid.length; this.n = grid[0].length; this.grid = grid; int initialHealth = health - grid[0][0]; if (initialHealth <= 0) { return false; } boolean[][] visited = new boolean[m][n]; return findPath(0, 0, initialHealth, visited); } private boolean findPath(int r, int c, int currentHealth, boolean[][] visited) { if (r == m - 1 && c == n - 1) { return true; } visited[r][c] = true; for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) { int nextHealth = currentHealth - grid[nr][nc]; if (nextHealth > 0) { if (findPath(nr, nc, nextHealth, visited)) { return true; } } } } visited[r][c] = false; // Backtrack return false; }}Complexity
Time
O(4^(m*n)) - In the worst case, the algorithm explores a number of paths that is exponential in the number of cells in the grid. This is because at each cell, there are up to 3 new directions to explore (excluding the one we came from).
Space
O(m * n) - This is for the recursion stack in the worst case, where the path could snake through every cell, and for the `visited` array.
Trade-offs
Pros
Conceptually simple and easy to understand for those familiar with recursion.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest grid sizes.
The recursion depth can be very large, potentially causing a stack overflow.
A more efficient approach is to treat this as a shortest path problem on a weighted graph. The grid cells act as vertices, and the cost to traverse to a cell is the health it deducts (0 or 1). Dijkstra's algorithm is ideal for finding the path with the minimum total cost from a single source. We find the minimum health reduction required to reach the destination. If this minimum cost is less than the initial health, a safe path exists.
Algorithm
- Model the grid as a graph where cells are vertices and adjacent cells are connected by edges.
- The weight of an edge moving into a cell
(r, c)isgrid[r][c]. - The problem becomes finding the shortest path (minimum health cost) from
(0, 0)to(m-1, n-1). - Initialize a
minCostarray with infinity to store the minimum cost to reach each cell. - Use a priority queue to store
(cost, row, col)tuples, prioritized by the lowestcost. - Start by adding
(grid[0][0], 0, 0)to the queue, but only ifhealth > grid[0][0]. - While the queue is not empty:
- Extract the cell
(r, c)with the minimum costc. - If this cell is the destination, return
true. - For each neighbor
(nr, nc):- Calculate the
newCost = c + grid[nr][nc]. - If
newCost < health(path is affordable) andnewCost < minCost[nr][nc](path is better), updateminCost[nr][nc]and add(newCost, nr, nc)to the queue.
- Calculate the
- Extract the cell
Walkthrough
We use Dijkstra's algorithm to find the path from (0, 0) to (m-1, n-1) that minimizes the total health lost. A 2D array, minCost, keeps track of the minimum health reduction to reach any cell. A priority queue is used to always explore the path with the currently lowest accumulated cost.
The algorithm is constrained by the health limit. We only explore a path to a neighbor if the new total cost does not exceed the available health. If we successfully reach the destination, it means we have found the cheapest possible path, and since all its intermediate steps were affordable, the path is safe.
import java.util.Arrays;import java.util.PriorityQueue; class Solution { public boolean canReach(int[][] grid, int health) { int m = grid.length; int n = grid[0].length; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int[][] minCost = new int[m][n]; for (int[] row : minCost) { Arrays.fill(row, Integer.MAX_VALUE); } PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); int initialCost = grid[0][0]; if (health <= initialCost) { return false; } minCost[0][0] = initialCost; pq.offer(new int[]{initialCost, 0, 0}); // {cost, row, col} while (!pq.isEmpty()) { int[] curr = pq.poll(); int cost = curr[0]; int r = curr[1]; int c = curr[2]; if (cost > minCost[r][c]) { continue; } if (r == m - 1 && c == n - 1) { return true; } for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int newCost = cost + grid[nr][nc]; if (newCost < health && newCost < minCost[nr][nc]) { minCost[nr][nc] = newCost; pq.offer(new int[]{newCost, nr, nc}); } } } } return false; }}Complexity
Time
O(m * n * log(m * n)) - With `V = m * n` vertices and `E = O(m * n)` edges, Dijkstra's with a binary heap has this complexity. Each vertex is processed once, and each edge relaxation involves a priority queue operation taking `O(log V)` time.
Space
O(m * n) - For the `minCost` array and the priority queue, which can store up to `m * n` elements in the worst case.
Trade-offs
Pros
A standard, correct, and robust algorithm for single-source shortest path problems.
Guaranteed to find the optimal path in terms of minimum health cost.
Efficient enough to pass the given constraints comfortably.
Cons
Slightly less efficient than 0-1 BFS for this specific problem since priority queue operations take logarithmic time, whereas a deque offers constant time operations.
The most efficient solution for this problem is a 0-1 Breadth-First Search (BFS). This is an optimization of Dijkstra's algorithm that applies when all edge weights in the graph are either 0 or 1. In our case, moving to a safe cell (grid[i][j] = 0) has a cost of 0, and moving to an unsafe cell (grid[i][j] = 1) has a cost of 1. By using a double-ended queue (deque) instead of a priority queue, we can achieve a linear time complexity.
Algorithm
- This approach is a specialized version of Dijkstra's for graphs with edge weights of only 0 and 1.
- Use a
minCostarray as in Dijkstra's. - Use a double-ended queue (deque) instead of a priority queue.
- Start by adding the starting cell
(0, 0)to the deque. - While the deque is not empty:
- Pop a cell
(r, c)from the front of the deque. - If it's the destination, return
true. - For each neighbor
(nr, nc):- Calculate
newCostas before. - If the path is affordable and better, update
minCost. - If the cost to enter the neighbor (
grid[nr][nc]) is 0, add the neighbor to the front of the deque. - If the cost is 1, add the neighbor to the back of the deque.
- Calculate
- Pop a cell
Walkthrough
The 0-1 BFS algorithm works by maintaining the core property of Dijkstra's—always processing the node with the minimum distance first—but without the overhead of a priority queue. It uses a deque. When exploring neighbors, if the connecting edge has a weight of 0, the neighbor is added to the front of the deque. If the edge has a weight of 1, it's added to the back.
This ensures that all cells reachable with a certain cost C are explored before any cells that require a cost of C+1. This makes the algorithm as effective as Dijkstra's but faster, as all deque operations (add/remove from front or back) are O(1).
import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque; class Solution { public boolean canReach(int[][] grid, int health) { int m = grid.length; int n = grid[0].length; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int[][] minCost = new int[m][n]; for (int[] row : minCost) { Arrays.fill(row, Integer.MAX_VALUE); } Deque<int[]> deque = new ArrayDeque<>(); int initialCost = grid[0][0]; if (health <= initialCost) { return false; } minCost[0][0] = initialCost; deque.offerFirst(new int[]{0, 0}); // {row, col} while (!deque.isEmpty()) { int[] curr = deque.pollFirst(); int r = curr[0]; int c = curr[1]; int cost = minCost[r][c]; if (r == m - 1 && c == n - 1) { return true; } for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int edgeCost = grid[nr][nc]; int newCost = cost + edgeCost; if (newCost < health && newCost < minCost[nr][nc]) { minCost[nr][nc] = newCost; if (edgeCost == 0) { deque.offerFirst(new int[]{nr, nc}); } else { deque.offerLast(new int[]{nr, nc}); } } } } } return false; }}Complexity
Time
O(m * n) - Each cell is enqueued and dequeued at most once. Since all deque operations are O(1), the total time complexity is linear in the number of vertices and edges.
Space
O(m * n) - For the `minCost` array and the deque, which can store up to `m * n` cells.
Trade-offs
Pros
The most efficient solution with a linear time complexity.
Optimal for graphs with only 0/1 edge weights.
Cons
The logic can be slightly less intuitive than a standard Dijkstra's implementation if one is not familiar with the 0-1 BFS optimization.
Solutions
Solution
class Solution {public boolean findSafeWalk(List<List<Integer>> grid, int health) { int m = grid.size(); int n = grid.get(0).size(); int[][] dist = new int[m][n]; for (int[] row : dist) { Arrays.fill(row, Integer.MAX_VALUE); } dist[0][0] = grid.get(0).get(0); Deque<int[]> q = new ArrayDeque<>(); q.offer(new int[]{0, 0}); final int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { int[] curr = q.poll(); int x = curr[0], y = curr[1]; for (int i = 0; i < 4; i++) { int nx = x + dirs[i]; int ny = y + dirs[i + 1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] > dist[x][y] + grid.get(nx).get(ny)) { dist[nx][ny] = dist[x][y] + grid.get(nx).get(ny); q.offer(new int[]{nx, ny}); } } } return dist[m - 1][n - 1] < health; }}class Solution {public: bool findSafeWalk(vector<vector<int>> &grid, int health) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dist(m, vector<int>(n, INT_MAX)); dist[0][0] = grid[0][0]; queue<pair<int, int>> q; q.emplace(0, 0); int dirs[5] = {-1, 0, 1, 0, -1}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nx = x + dirs[i]; int ny = y + dirs[i + 1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] > dist[x][y] + grid[nx][ny]) { dist[nx][ny] = dist[x][y] + grid[nx][ny]; q.emplace(nx, ny); } } } return dist[m - 1][n - 1] < health; }};class Solution: def findSafeWalk(self, grid: List[List[int]], health: int) -> bool: m, n = len(grid), len(grid[0]) dist = [[inf] * n for _ in range(m)] dist[0][0] = grid[0][0] q = deque([(0, 0)]) dirs = (- 1, 0, 1, 0, - 1) while q: x, y = q . popleft() for a, b in pairwise(dirs): nx, ny = x + a, y + b if (0 <= nx < m and 0 <= ny < n and dist[nx][ny] > dist[x][y] + grid[nx][ny]): dist[nx][ny] = dist[x][y] + grid[nx][ny] q . append((nx, ny)) return dist[- 1][- 1] < healthVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.