This problem requires evaluating a grid where each cell may decrease your health. Using breadth-first search with careful tracking of remaining health ensures you only explore feasible paths. Prioritizing cells that consume less health allows efficient determination of whether the lower-right corner is reachable safely.
Problem Statement
Given an m x n binary matrix grid and an integer health, determine if you can reach the bottom-right corner starting from the top-left corner. You may move in four directions: up, down, left, or right, but your health must remain positive at each step.
Cells with value 1 reduce your health by 1 upon entering. Your goal is to find a path from (0, 0) to (m - 1, n - 1) such that you never run out of health. Return true if such a path exists, otherwise return false.
Examples
Example 1
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
Output: true
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
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
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.length
- n == grid[i].length
- 1 <= m, n <= 50
- 2 <= m * n
- 1 <= health <= m + n
- grid[i][j] is either 0 or 1.
Solution Approach
Breadth-First Search with Health Tracking
Use a BFS queue to explore each cell while tracking remaining health. Only enqueue moves that keep health positive. This guarantees the search only follows viable paths.
Use 01 BFS Optimization
Treat cells with 0 cost as higher priority and cells with 1 cost as lower priority, using a deque to push 0-cost cells to the front. This minimizes unnecessary expansions and efficiently finds the safest path.
Avoid Revisiting Inferior States
Keep a matrix to record the maximum remaining health at each cell. Skip any state where the current health is less than the recorded value to prevent redundant exploration and reduce runtime.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(mn) in the worst case, as each cell is visited at most once with the highest health. Space complexity is also O(mn) for the BFS queue and health tracking matrix.
What Interviewers Usually Probe
- Candidate immediately considers BFS with health tracking, not plain DFS.
- Candidate optimizes with 01 BFS to handle cells with different costs efficiently.
- Candidate handles boundary conditions and health depletion correctly during traversal.
Common Pitfalls or Variants
Common pitfalls
- Failing to track health properly can lead to incorrect true/false results.
- Revisiting cells without comparing remaining health can cause TLE or wrong paths.
- Ignoring cells with value 1 as costly can result in paths that falsely appear safe.
Follow-up variants
- Change movement to include diagonals and recalculate paths.
- Vary the health decrement for different cells instead of 1 per obstacle.
- Determine the minimum starting health needed to guarantee a safe walk.
How GhostInterview Helps
- Automatically highlights the BFS + health tracking pattern critical for this problem.
- Shows the correct usage of 01 BFS prioritization to avoid unnecessary expansions.
- Visualizes safe paths and remaining health at each step to verify correctness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern for Find a Safe Walk Through a Grid?
It is graph traversal using BFS with careful tracking of remaining health points.
How do I know when to use 01 BFS in this problem?
Use 01 BFS when cells have cost 0 or 1, pushing 0-cost moves to the front of the deque to optimize exploration.
Can I move diagonally in this problem?
No, only up, down, left, or right moves are allowed according to the problem constraints.
What happens if health reaches zero in the middle of the grid?
You cannot enter a cell that would reduce health to zero or below; such paths are unsafe.
How should I track visited states to avoid redundant work?
Store the maximum remaining health at each cell and skip processing if the current health is less than the recorded value.
Need direct help with Find a Safe Walk Through a Grid instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find a Safe Walk Through a Grid from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the fastest path in a grid where each cell has a minimum time requirement using BFS and priority queue techniques.
Open problem page#2290 Minimum Obstacle Removal to Reach CornerFind the minimum obstacles to remove in a 2D grid to reach the bottom-right corner using BFS graph traversal techniques.
Open problem page#3341 Find Minimum Time to Reach Last Room IFind Minimum Time to Reach Last Room I challenges you to determine the minimum time to travel in a dungeon with a grid layout.
Open problem page