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.Problem Overview: You are given a matrix where each cell affects your health while walking through it. Starting from the top-left cell, determine whether you can reach the bottom-right cell without your health dropping to zero or below. Movement is allowed in four directions, and each step reduces health based on the grid value.
Approach 1: Breadth-First Search (BFS) with State Pruning (Time: O(m*n), Space: O(m*n))
This approach models the grid as a graph and performs a Breadth-First Search starting from (0,0). Each state keeps track of the current cell and the remaining health after entering that cell. While exploring neighbors, compute the new health after applying the cell's cost. If the remaining health becomes zero or negative, that path is invalid and skipped. To avoid revisiting weaker states, maintain a matrix that stores the maximum health seen at each cell. Only continue traversal when you arrive with strictly more remaining health than before. This pruning keeps the exploration bounded and ensures every cell is processed only a limited number of times.
The BFS queue processes cells level by level, exploring four directions (up, down, left, right). As soon as the bottom-right cell is reached with positive health, the walk is valid. The grid behaves like a graph where nodes are cells and edges represent moves between adjacent cells.
Approach 2: Depth-First Search (DFS) with Memoization (Time: O(m*n), Space: O(m*n))
This strategy explores paths recursively using Depth-First Search. From each cell, attempt to move in four directions while subtracting the cell's health cost. The key optimization is memoization: store the maximum remaining health previously recorded for each cell. If the DFS revisits a cell with less or equal health than a prior visit, that branch is abandoned immediately. This prevents exponential exploration and converts the search into a bounded traversal.
The recursion continues until either the health becomes non‑positive (invalid path) or the destination cell is reached. DFS with memoization works well because the grid size is limited and repeated states are aggressively pruned using the stored best-health values.
Recommended for interviews: The BFS approach is typically preferred. It mirrors standard grid traversal problems and clearly demonstrates how to combine graph traversal with state pruning. DFS with memoization also works and shows strong understanding of recursion and dynamic state caching, but BFS tends to be easier to reason about and debug during interviews.
This approach uses the Breadth-First Search algorithm to find the shortest path from the top-left corner of the grid to the bottom-right corner while maintaining a positive health level. We explore all possible paths from the start, tracking the health remaining at each step. We use a queue to facilitate the level-order traversal typical of BFS and check each possible move (up, down, left, right) from the current position.
The BFS method starts at (0,0) with the given health. We use a deque for level-wise traversal of the next reachable cells, maintaining a visited set to avoid revisiting cells. We explore possible directions (up, down, left, right) and check for boundary conditions and revisit prevention. The method returns true if we reach the target cell (m-1, n-1) with positive health.
Time Complexity: O(m*n) - since we in the worst case visit each cell once.
Space Complexity: O(m*n) - due to the visited set and queue storage.
This approach applies a depth-first search strategy with memorization to explore paths from the top-left to the bottom-right of the grid. By using a stack, it simulates DFS traversal, recursively checking viable movements. Memorization avoids redundant computations by storing previously calculated results for specific grid positions with remaining health. This optimization increases efficiency and reduces unnecessary recursion.
We leverage a recursive DFS approach where each node in the recursion tree represents a grid cell with current health. We recursively explore all possible valid directions, utilizing a memoization dictionary memo to cache results and avoid redundant calculations. The base case checks if the target is reached, at which point the function returns true.
Time Complexity: O(m*n*health) - Due to potentially exploring paths with overlapping health conditions.
Space Complexity: O(m*n*health) - Memoization storage for each combination of grid position and health.
We define a 2D array dist, where dist[i][j] represents the minimum health value required to reach position (i, j) from the top-left corner. Initially, we set dist[0][0] to grid[0][0] and add (0, 0) to the queue q.
Then, we continuously take elements (x, y) from the queue and try to move in four directions. If we move to a valid position (nx, ny) and the health value required to move from (x, y) to (nx, ny) is smaller, we update dist[nx][ny] = dist[x][y] + grid[nx][ny] and add (nx, ny) to the queue q.
Finally, when the queue is empty, we obtain dist[m-1][n-1], which is the minimum health value required to reach the bottom-right corner from the top-left corner. If this value is less than health, then we can reach the bottom-right corner; otherwise, we cannot.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(m*n) - since we in the worst case visit each cell once. Space Complexity: O(m*n) - due to the visited set and queue storage. |
| Depth-First Search (DFS) with Memorization | Time Complexity: O(m*n*health) - Due to potentially exploring paths with overlapping health conditions. Space Complexity: O(m*n*health) - Memoization storage for each combination of grid position and health. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) with health tracking | O(m*n) | O(m*n) | Best general solution for grid traversal with constraints and pruning |
| DFS with Memoization | O(m*n) | O(m*n) | Useful when implementing recursive exploration with cached states |
Find a Safe Walk Through a Grid || LeetCode Biweekly Contest 139 || Leetcode Solution • codi • 1,589 views views
Watch 7 more video solutions →Practice Find a Safe Walk Through a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor