LeetCode 3286 - Find a Safe Walk Through a Grid

The problem requires determining whether there exists a path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) in a binary m x n matrix grid, while maintaining a health value greater than or equal to 1.

leetcodemediumarraybreadth-first-searchgraph-theoryheap-(priority-queue)matrixshortest-path

LeetCode Problem 3286

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path

Solution

Problem Understanding

The problem requires determining whether there exists a path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) in a binary m x n matrix grid, while maintaining a health value greater than or equal to 1. Each cell with a value of 1 is considered unsafe and reduces your health by 1 when entered. Cells with a value of 0 do not affect your health. Movement is allowed in the four cardinal directions: up, down, left, and right. The starting health is given by the health parameter.

The input is a small grid (up to 50 x 50), so brute-force recursion is technically feasible but can be optimized. Important constraints include health <= m + n, meaning that the health is at most the length of a path if it only moves right and down. Edge cases to consider include starting or ending on unsafe cells, having minimal health, or having a fully blocked grid where no path exists.

The goal is to return true if a path exists such that the health never drops below 1, and false otherwise.

Approaches

A brute-force approach would attempt to explore all possible paths from (0, 0) to (m - 1, n - 1) recursively, keeping track of remaining health at each step. For each move, you would reduce health by 1 if the cell is unsafe and backtrack if the health drops to zero. This is correct in principle but exponential in time complexity (O(4^(m*n)) in the worst case), which is impractical for grids up to 50 x 50.

The optimal approach is a variation of BFS (Breadth-First Search) with a priority queue or a visited-state matrix that tracks the maximum remaining health at each cell. Instead of exploring all paths blindly, the BFS ensures that we only continue exploring paths where the remaining health is higher than any previously recorded health at the same cell. This prevents redundant exploration of worse paths while guaranteeing correctness.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^(m*n)) O(m*n) Recursive DFS exploring all paths; exponential and impractical
Optimal O(m*n) O(m*n) BFS with state tracking of max health at each cell; only explore better health paths

Algorithm Walkthrough

  1. Initialize a queue to perform BFS starting from (0, 0) with the initial health.
  2. Create a 2D array max_health of size m x n to store the maximum remaining health recorded at each cell.
  3. Push the initial state (0, 0, health) into the queue and set max_health[0][0] = health.
  4. While the queue is not empty, pop the current state (x, y, h).
  5. If (x, y) is the destination (m - 1, n - 1) and h >= 1, return true.
  6. Iterate over the four possible directions. For each valid neighboring cell (nx, ny):

a. Calculate nh = h - grid[nx][ny].

b. If nh < 1, skip this neighbor since health would be zero or negative.

c. If nh is greater than the previously recorded max_health[nx][ny], update max_health[nx][ny] = nh and enqueue (nx, ny, nh). 7. If the queue is exhausted without reaching the destination with positive health, return false.

Why it works: BFS ensures that all reachable states are explored in increasing order of path length. The max_health matrix guarantees that we only continue exploring paths with strictly better remaining health than previously encountered, preventing cycles and redundant exploration. This ensures correctness and efficiency.

Python Solution

from collections import deque
from typing import List

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        max_health = [[-1] * n for _ in range(m)]
        queue = deque([(0, 0, health)])
        max_health[0][0] = health

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            x, y, h = queue.popleft()
            if (x, y) == (m - 1, n - 1) and h >= 1:
                return True

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    nh = h - grid[nx][ny]
                    if nh >= 1 and nh > max_health[nx][ny]:
                        max_health[nx][ny] = nh
                        queue.append((nx, ny, nh))
        return False

The Python implementation sets up a BFS using a queue and a max_health matrix to track the best health achieved at each cell. The loop explores neighbors in all four directions, pruning paths that cannot maintain positive health or are worse than previously recorded states. The algorithm terminates early once a valid path reaches the destination.

Go Solution

package main

func findSafeWalk(grid [][]int, health int) bool {
    m, n := len(grid), len(grid[0])
    maxHealth := make([][]int, m)
    for i := range maxHealth {
        maxHealth[i] = make([]int, n)
        for j := range maxHealth[i] {
            maxHealth[i][j] = -1
        }
    }

    type state struct {
        x, y, h int
    }

    queue := []state{{0, 0, health}}
    maxHealth[0][0] = health
    directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]

        if curr.x == m-1 && curr.y == n-1 && curr.h >= 1 {
            return true
        }

        for _, d := range directions {
            nx, ny := curr.x+d[0], curr.y+d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n {
                nh := curr.h - grid[nx][ny]
                if nh >= 1 && nh > maxHealth[nx][ny] {
                    maxHealth[nx][ny] = nh
                    queue = append(queue, state{nx, ny, nh})
                }
            }
        }
    }
    return false
}

The Go implementation mirrors the Python version, using slices for the queue and maxHealth matrix. The state struct encapsulates coordinates and remaining health. The BFS loop processes the queue efficiently and prunes paths with insufficient health or previously visited worse states.

Worked Examples

Example 1:

grid = [[0,1,0,0,0],
        [0,1,0,1,0],
        [0,0,0,1,0]], health = 1

Step-by-step BFS exploration:

Step Queue Contents max_health
Initial [(0,0,1)] [[1,-1,-1,-1,-1],[ -1,-1,-1,-1,-1],[ -1,-1,-1,-1,-1]]
Pop (0,0,1) [(1,0,1)] update max_health[1][0]=1
Pop (1,0,1) [(2,0,1),(1,1,0)] skip (1,1,0)
Pop (2,0,1) [(2,1,1)] update max_health[2][1]=1
Pop (2,1,1) [(2,2,1)] update max_health[2][2]=1
Pop (2,2,1) [(1,2,0),(2,3,0)] skip invalid nh<1
Continue reach (2,4,1) destination reached

Return true.

Example 2: BFS exploration eventually fails to reach the bottom-right cell with health >= 1 because all paths require at least 4 health. Return false.

Example 3: BFS finds a path avoiding (1,1) with initial health 5 and safely reaches the destination. Return true.

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Each cell is processed at most once for each possible remaining health value, but due to max_health pruning, each cell is effectively visited once.
Space O(m*n) max_health matrix stores one integer per cell and queue size is proportional to the number of reachable cells.

The reasoning relies on the pruning condition nh > max_health[nx][ny], which prevents redundant exploration of worse paths.

Test Cases

# Provided examples
assert Solution().findSafeWalk([[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], 1) == True  # Example 1
assert Solution().find