Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] 1
[[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]] 3
[[1,1,1],[1,0,1],[1,1,1]] 5
shortest-path-in-a-grid-with-obstacles-elimination)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
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;
}
}
// Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
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
}
# Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
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] < health
// Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
// 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;
// }
// }
// Accepted solution for LeetCode #3286: Find a Safe Walk Through a Grid
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.