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.
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; }}Video 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.