Find a Safe Walk Through a Grid solution and explanation
Google
9 more videos on this problem
Find a Safe Walk Through a Grid | Leetcode 3286 | Made Easy | Graph Concepts & Qns - 50 | MIKcodestorywithMIK · 24:47 · 6K views
Find a Safe Walk Through a Grid 🔥 Leetcode 3286 | BFS + Minimum Cost Path Study Placement · 39:04 · 1K views
3286. Find a Safe Walk Through a Grid (Leetcode Medium)Programming Live with Larry · 12:26 · 889 views
3286. Find a Safe Walk Through a Grid | Leetcode Daily - PythonLeetcode Daily · 6:03 · 696 views
Leetcode 3286 | Find a Safe Walk Through a Grid | Biweekly Contest 139Road To FAANG · 7:45 · 632 views
Find a Safe Walk Through a Grid | LeetCode 3286 - Pythonimpoldev · 14:29 · 490 views
Find a Safe Walk Through a Grid | Leetcode - 3286Shivam Gupta · 11:39 · 447 views
Daily Leetcode #2284: Jul 02, 2026 - 3286. Find a Safe Walk Through a GridProgramming Live with Larry · 10:56 · 366 views
[English] 3286. Find a Safe Walk Through a Grid - Q2 Biweekly 139 [Leetcode Medium]Romain Lhotte · 8:03 · 190 views
3286. Find a Safe Walk Through a Grid | POTD 2 July 2026 | C++ | LeetcodeTechie On Track · 9:55 · 77 views
The problem
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.
Approach overview
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.
Approach 1: Breadth-First Search (BFS)
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.
from collections import deque
def canReachEndBFS(grid, health):
m, n = len(grid), len(grid[0])
queue = deque([(0, 0, health)]) # (x, y, remaining health)
visited = set()
visited.add((0, 0))
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
x, y, h = queue.popleft()
if (x, y) == (m - 1, n - 1) and h > 0:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
new_health = h - grid[nx][ny]
if new_health > 0:
queue.append((nx, ny, new_health))
visited.add((nx, ny))
return Falseimport java.util.*;
public class GridPath {
public boolean canReachEndBFS(int[][] grid, int health) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
queue.add(new int[]{0, 0, health});
visited[0][0] = true;
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1], h = cell[2];
if (x == m - 1 && y == n - 1 && h > 0) {
return true;
}
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
int newHealth = h - grid[nx][ny];
if (newHealth > 0) {
queue.add(new int[]{nx, ny, newHealth});
visited[nx][ny] = true;
}
}
}
}
return false;
}
}#include <vector>
#include <queue>
#include <tuple>
using namespace std;
bool canReachEndBFS(const vector<vector<int>>& grid, int health) {
int m = grid.size();
int n = grid[0].size();
queue<tuple<int, int, int>> q;
q.emplace(0, 0, health);
vector<vector<bool>> visited(m, vector<bool>(n, false));
visited[0][0] = true;
int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!q.empty()) {
auto [x, y, h] = q.front();
q.pop();
if (x == m - 1 && y == n - 1 && h > 0) {
return true;
}
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
int new_health = h - grid[nx][ny];
if (new_health > 0) {
q.emplace(nx, ny, new_health);
visited[nx][ny] = true;
}
}
}
}
return false;
}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.
Approach 2: Depth-First Search (DFS) with Memorization
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.
def canReachEndDFS(grid, health):
def dfs(x, y, h, memo):
if x == len(grid) - 1 and y == len(grid[0]) - 1:
return h > 0
if (x, y, h) in memo:
return memo[(x, y, h)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
if h - grid[nx][ny] > 0 and dfs(nx, ny, h - grid[nx][ny], memo):
memo[(x, y, h)] = True
return True
memo[(x, y, h)] = False
return False
return dfs(0, 0, health, {})import java.util.HashMap;
public class GridPathDFS {
private boolean dfs(int x, int y, int h, int[][] grid, HashMap<String, Boolean> memo) {
if (x == grid.length - 1 && y == grid[0].length - 1) {
return h > 0;
}
String key = x + "," + y + "," + h;
if (memo.containsKey(key)) {
return memo.get(key);
}
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
int newHealth = h - grid[nx][ny];
if (newHealth > 0 && dfs(nx, ny, newHealth, grid, memo)) {
memo.put(key, true);
return true;
}
}
}
memo.put(key, false);
return false;
}
public boolean canReachEndDFS(int[][] grid, int health) {
return dfs(0, 0, health, grid, new HashMap<>());
}
}#include <vector>
#include <unordered_map>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> State;
bool dfs(int x, int y, int h, const vector<vector<int>>& grid, unordered_map<State, bool>& memo) {
if (x == grid.size() - 1 && y == grid[0].size() - 1) {
return h > 0;
}
State current = make_tuple(x, y, h);
if (memo.find(current) != memo.end()) {
return memo[current];
}
int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
int new_health = h - grid[nx][ny];
if (new_health > 0 && dfs(nx, ny, new_health, grid, memo)) {
return memo[current] = true;
}
}
}
return memo[current] = false;
}
bool canReachEndDFS(const vector<vector<int>>& grid, int health) {
unordered_map<State, bool> memo;
return dfs(0, 0, health, grid, memo);
}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.
Approach 3: BFS
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.
function findSafeWalk(grid: number[][], health: number): boolean {
const m = grid.length;
const n = grid[0].length;
const dist: number[][] = Array.from({ length: m }, () => Array(n).fill(Infinity));
dist[0][0] = grid[0][0];
const q: [number, number][] = [[0, 0]];
const dirs = [-1, 0, 1, 0, -1];
while (q.length > 0) {
const [x, y] = q.shift()!;
for (let i = 0; i < 4; i++) {
const nx = x + dirs[i];
const 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.push([nx, ny]);
}
}
}
return dist[m - 1][n - 1] < health;
}func findSafeWalk(grid [][]int, health int) bool {
m, n := len(grid), len(grid[0])
dist := make([][]int, m)
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = math.MaxInt32
}
}
dist[0][0] = grid[0][0]
q := [][2]int{{0, 0}}
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
curr := q[0]
q = q[1:]
x, y := curr[0], curr[1]
for i := 0; i < 4; i++ {
nx, ny := x+dirs[i], 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 = append(q, [2]int{nx, ny})
}
}
}
return dist[m-1][n-1] < health
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find a Safe Walk Through a Grid easy or hard?
The problem is rated Medium because it combines grid traversal with state management. The main challenge is pruning revisits using the best remaining health at each cell, which prevents exponential exploration.
Find a Safe Walk Through a Grid Python/Java solution
Typical implementations use BFS with a queue and a 2D array for tracking maximum remaining health. Python solutions commonly use collections.deque, while Java implementations rely on ArrayDeque or a standard queue structure. Both follow the same O(m*n) traversal logic.
How to solve Find a Safe Walk Through a Grid in O(m*n)?
Traverse the grid using BFS while tracking remaining health after entering each cell. Maintain a matrix storing the maximum health recorded at every position. Only push a new state into the queue if the remaining health is positive and better than the previous best for that cell. This pruning ensures each cell is processed a limited number of times, resulting in O(m*n) complexity.
What is the best approach for Find a Safe Walk Through a Grid?
Breadth-First Search with state pruning is the most reliable approach. Each BFS state stores the current cell and remaining health. A matrix tracks the maximum health previously seen at each cell, preventing weaker revisits. This keeps the traversal efficient with O(m*n) time and space complexity.
Is Find a Safe Walk Through a Grid asked at Google/Amazon/Meta?
Grid traversal problems that combine BFS, state pruning, and shortest-path style reasoning are common in interviews at companies like Amazon, Google, and Meta. Variants often involve health constraints, weighted cells, or path feasibility checks in a matrix.
What data structure is used in Find a Safe Walk Through a Grid?
The core data structures are a queue for BFS traversal and a 2D matrix to store the best remaining health seen at each cell. The grid itself is treated as a graph where each cell connects to up to four neighbors.
What is the time complexity of Find a Safe Walk Through a Grid?
Both BFS with pruning and DFS with memoization run in O(m*n) time where m and n are the grid dimensions. Each cell is processed only when you arrive with better remaining health than before. Space complexity is also O(m*n) due to the visited or memoization matrix.