Skip to main content
Talentd

Find a Safe Walk Through a Grid - Solution & Explanation

MediumArrayBreadth-First SearchGraphHeap (Priority Queue)17 min readAsked at: Meta, Google, Bloomberg
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 2 <= m * n
  • 1 <= health <= m + n
  • grid[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.

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.

Code

PythonC++Java

Python

C++

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++Java

Python

C++

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS) with health trackingO(m*n)O(m*n)Best general solution for grid traversal with constraints and pruning
DFS with MemoizationO(m*n)O(m*n)Useful when implementing recursive exploration with cached states

Video Solution

Find a Safe Walk Through a Grid | Leetcode 3286 | Made Easy | Graph Concepts & Qns - 50 | MIK • codestorywithMIK • 6,574 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find a Safe Walk Through a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shortest Path in a Grid with Obstacles Elimination