Find a Safe Walk Through a Grid

Find a Safe Walk Through a Grid

What is this problem about?

The Find a Safe Walk Through a Grid interview question involves navigating a 2D grid where some cells contain "hazards" or obstacles that reduce your "health" or "safety" points. You start at the top-left corner with a specific amount of initial health and want to reach the bottom-right corner. Each time you step into a cell with a hazard, your health decreases. You need to determine if there is a path where you can reach the destination with at least 1 health point remaining.

Why is this asked in interviews?

Google and Bloomberg use this to test a candidate's proficiency with graph traversal and optimization. It's essentially a shortest-path problem where the "distance" is the health cost. It evaluations your ability to use the Breadth-First Search interview pattern or Dijkstra's algorithm to find the path that minimizes damage taken. It also checks how you handle state management within a grid.

Algorithmic pattern used

This problem is best solved using Dijkstra's Algorithm or 0-1 BFS. Since you want to maximize your remaining health, you are essentially looking for the "shortest path" in terms of health cost. You can maintain a max_health_at[r][c] 2D array to store the maximum health you can have when reaching each cell. A Heap (Priority Queue) can be used to always explore the cell where you currently have the highest health.

Example explanation

Grid ($2 imes 2$):

[0, 1]
[0, 0]

Initial Health: 2.

1. Start at (0,0). Health becomes 2 - grid[0][0] = 2.
2. Option A: Move to (0,1). Hazard! Health becomes 2 - 1 = 1.
3. Option B: Move to (1,0). No hazard. Health becomes 2 - 0 = 2.
4. From (1,0), move to (1,1). No hazard. Health stays 2.
5. Destination reached with health 2. Result: True.

Common mistakes candidates make

• Simple BFS for shortest distance: A standard BFS finds the path with the fewest steps, not the path with the lowest cost. These are not always the same.
• Not updating state: Failing to re-visit a cell if a new path reaches it with more health than previously recorded.
• Incorrect initialization: Not accounting for the health cost of the starting cell itself.

Interview preparation tip

When you see a grid problem involving "costs," "health," or "weights," immediately think of Dijkstra's algorithm. If the costs are only 0 and 1, you can use a Deque (0-1 BFS) to achieve $O(V+E)$ time complexity, which is faster than a Priority Queue.