Find a Safe Walk Through a Grid - Video Solutions

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.