Problem Description

You have an m x n binary grid and a starting health value. Your goal is to navigate from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) while keeping your health positive.

Movement Rules:

• You can move in four directions: up, down, left, or right to adjacent cells
• You can only move if your health remains positive after the move

Health Mechanics:

• You start with an initial health value
• Cells with grid[i][j] = 1 are unsafe and reduce your health by 1 when you enter them
• Cells with grid[i][j] = 0 are safe and don't affect your health

Objective: Determine if it's possible to reach the destination cell (m-1, n-1) with at least 1 health point remaining. Return true if possible, false otherwise.

Example: If you have a grid where some cells are unsafe (value 1), you need to find if there exists a path from start to finish that doesn't reduce your health below 1. The path doesn't have to be the shortest - it just needs to preserve enough health to reach the destination alive.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and adjacent cells are connected by edges. We need to find a path from the start node (0,0) to the end node (m-1, n-1).

Is it a tree?

• No: The grid structure is not a tree. There can be multiple paths between cells, and cycles are possible when moving in four directions.

Is the problem related to directed acyclic graphs?

• No: The grid allows movement in all four directions, which means it can have cycles. It's not a DAG.

Is the problem related to shortest paths?

• Yes: We need to find the path with minimum health reduction (or minimum cost) from start to finish. This is essentially finding the shortest/optimal path in terms of health cost.

Is the graph Weighted?

• No: While cells have different costs (0 or 1), this is more about uniform edge weights where each move has the same weight, but nodes have different costs. The problem can be solved with BFS by tracking the minimum cost to reach each cell.

Conclusion: BFS The flowchart leads us to BFS (Breadth-First Search). This makes sense because:

• We're exploring a grid graph level by level
• We need to find the minimum health cost path
• BFS can efficiently track the minimum cost to reach each cell
• The solution uses a queue-based approach with distance tracking, which is characteristic of BFS

The algorithm maintains a distance array to track the minimum health reduction needed to reach each cell, updating it as we explore the grid using BFS traversal.

Intuition

When we think about this problem, we need to find if there's a path from start to finish that doesn't drain our health completely. The key insight is that we want to minimize the total health lost along any path.

Instead of tracking our remaining health as we explore (which would be complicated since we could reach the same cell with different health values), we can flip the problem: track the minimum health cost required to reach each cell.

This transforms the problem into finding the path with minimum cost. If we know the minimum health needed to reach any cell, we can simply check if the minimum health needed to reach the destination is less than our starting health.

Why BFS works here:

1. Level-by-level exploration: BFS explores cells in waves, allowing us to systematically check all possible paths
2. Optimal substructure: The minimum cost to reach a cell depends on the minimum costs to reach its neighbors
3. Update when better: As we explore, we only update a cell's cost when we find a cheaper way to reach it

The clever part is using a dist array where dist[i][j] represents the minimum health points we'd lose to reach cell (i, j). We start with dist[0][0] = grid[0][0] (the cost of the starting cell itself).

As we process each cell from the queue, we check all four adjacent cells. If moving to an adjacent cell gives us a lower total cost than what we previously recorded, we update it and add that cell back to the queue for further exploration.

This approach ensures we always find the path with minimum health loss. At the end, if dist[m-1][n-1] < health, we know we can reach the destination with health remaining.

Learn more about Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements BFS to find the minimum health cost path from the top-left to the bottom-right corner.

Data Structures Used:

• dist: A 2D array where dist[i][j] stores the minimum health points lost to reach cell (i, j)
• q: A deque (double-ended queue) for BFS traversal
• dirs: A tuple storing direction vectors (-1, 0, 1, 0, -1) for efficient iteration

Algorithm Steps:

1. Initialize the distance matrix:

   • Create dist with all values set to infinity (inf)
   • Set dist[0][0] = grid[0][0] (starting cell's cost)
   • Add starting position (0, 0) to the queue

2. BFS traversal:

   • While the queue is not empty:
     • Dequeue a cell (x, y)
     • Check all four adjacent cells using pairwise(dirs)
       • This cleverly generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
     • For each valid adjacent cell (nx, ny):
       • Calculate new cost: dist[x][y] + grid[nx][ny]
       • If this cost is less than dist[nx][ny]:
         • Update dist[nx][ny] with the new minimum cost
         • Add (nx, ny) to the queue for further exploration

3. Check the result:

   • After BFS completes, dist[m-1][n-1] contains the minimum health lost
   • Return True if dist[m-1][n-1] < health, meaning we can reach the destination with health remaining

Key Optimization: The algorithm only adds a cell back to the queue when we find a better (lower cost) path to it. This ensures we explore all possible paths efficiently while maintaining the minimum cost to each cell.

Time Complexity: O(m × n) where each cell can be visited multiple times in worst case Space Complexity: O(m × n) for the distance matrix and queue

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• Grid: [[0, 1], [1, 0]] (2x2 grid)
• Initial health: 3
• Start: (0, 0), Destination: (1, 1)

Grid visualization:
[0, 1]  -> 0 = safe, 1 = unsafe (-1 health)
[1, 0]

Step 1: Initialization

• Create dist matrix initialized with infinity:

  dist = [[inf, inf],
          [inf, inf]]

• Set dist[0][0] = grid[0][0] = 0 (starting cell cost)

  dist = [[0, inf],
          [inf, inf]]

• Add (0, 0) to queue: q = [(0, 0)]

Step 2: Process (0, 0)

• Dequeue (0, 0)

• Check adjacent cells:

  • Right (0, 1): valid
    • New cost = dist[0][0] + grid[0][1] = 0 + 1 = 1
    • Current dist[0][1] = inf
    • Since 1 < inf, update dist[0][1] = 1 and add (0, 1) to queue
  • Down (1, 0): valid
    • New cost = dist[0][0] + grid[1][0] = 0 + 1 = 1
    • Current dist[1][0] = inf
    • Since 1 < inf, update dist[1][0] = 1 and add (1, 0) to queue

  dist = [[0, 1],
          [1, inf]]
  q = [(0, 1), (1, 0)]

Step 3: Process (0, 1)

• Dequeue (0, 1)

• Check adjacent cells:

  • Left (0, 0): cost would be 1 + 0 = 1, but dist[0][0] = 0 is already better
  • Down (1, 1): valid
    • New cost = dist[0][1] + grid[1][1] = 1 + 0 = 1
    • Current dist[1][1] = inf
    • Since 1 < inf, update dist[1][1] = 1 and add (1, 1) to queue

  dist = [[0, 1],
          [1, 1]]
  q = [(1, 0), (1, 1)]

Step 4: Process (1, 0)

• Dequeue (1, 0)
• Check adjacent cells:
  • Up (0, 0): cost would be 1 + 0 = 1, but dist[0][0] = 0 is already better
  • Right (1, 1):
    • New cost = dist[1][0] + grid[1][1] = 1 + 0 = 1
    • Current dist[1][1] = 1
    • Since 1 = 1 (not less), no update needed

Step 5: Process (1, 1)

• Dequeue (1, 1)
• Check adjacent cells:
  • Up (0, 1): cost would be 1 + 1 = 2, but dist[0][1] = 1 is already better
  • Left (1, 0): cost would be 1 + 1 = 2, but dist[1][0] = 1 is already better

Final Result:

• dist[1][1] = 1 (minimum health lost to reach destination)
• Since 1 < 3 (health), return True

The algorithm found two equally good paths:

1. (0,0) → (0,1) → (1,1) with health loss: 0 + 1 + 0 = 1
2. (0,0) → (1,0) → (1,1) with health loss: 0 + 1 + 0 = 1

Both paths lose only 1 health point, leaving us with 2 health remaining at the destination.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × m × n) where m is the number of rows and n is the number of columns in the grid.

The algorithm uses BFS with a deque. In the worst case, each cell (x, y) can be visited multiple times - specifically, it can be added to the queue whenever a shorter distance is found from any of its neighbors. Since we don't use a visited set and rely only on distance comparison, a cell can potentially be processed up to O(m × n) times (once for each possible path leading to it). With m × n total cells, this gives us O(m × n × m × n) time complexity.

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grid.

The space is used for:

• The dist matrix: O(m × n)
• The deque q: In the worst case, it can contain all cells, which is O(m × n)
• Other variables use constant space

Therefore, the total space complexity is O(m × n).

Note: The reference answer suggests O(m × n) time complexity, which would be achievable with Dijkstra's algorithm using a priority queue or with 0-1 BFS (using deque with appendleft for 0-weight edges). However, the given implementation doesn't optimize for this and may revisit cells multiple times, leading to a higher time complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Standard BFS Instead of 0-1 BFS

The current solution uses a standard BFS with a regular deque, which can lead to suboptimal performance and potentially incorrect results when cells are revisited multiple times.

The Problem:

• Standard BFS doesn't guarantee that when we first visit a cell, we've found the minimum cost path to it
• This causes cells to be added to the queue multiple times, leading to redundant processing
• In worst case, a cell could be processed O(m×n) times

The Solution - 0-1 BFS: Since the grid only contains 0s and 1s (weights of 0 or 1), we can optimize using 0-1 BFS:

from collections import deque

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        distance = [[inf] * cols for _ in range(rows)]
        distance[0][0] = grid[0][0]
      
        # Use deque for 0-1 BFS
        queue = deque([(0, 0)])
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
      
        while queue:
            x, y = queue.popleft()
          
            # Skip if we've already found a better path
            if distance[x][y] < distance[x][y]:
                continue
              
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
              
                if 0 <= nx < rows and 0 <= ny < cols:
                    new_cost = distance[x][y] + grid[nx][ny]
                  
                    if new_cost < distance[nx][ny]:
                        distance[nx][ny] = new_cost
                      
                        # Key optimization: add to front if safe cell (0), back if unsafe (1)
                        if grid[nx][ny] == 0:
                            queue.appendleft((nx, ny))
                        else:
                            queue.append((nx, ny))
      
        return distance[-1][-1] < health

2. Not Using Dijkstra's Algorithm for Guaranteed Optimality

For complete correctness and optimal performance, Dijkstra's algorithm with a priority queue is more appropriate:

import heapq

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        rows, cols = len(grid), len(grid[0])
      
        # Priority queue: (cost, x, y)
        pq = [(grid[0][0], 0, 0)]
        visited = set()
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
      
        while pq:
            cost, x, y = heapq.heappop(pq)
          
            # Skip if already visited
            if (x, y) in visited:
                continue
              
            visited.add((x, y))
          
            # Check if we reached destination
            if x == rows - 1 and y == cols - 1:
                return cost < health
          
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
              
                if (0 <= nx < rows and 0 <= ny < cols and 
                    (nx, ny) not in visited):
                    heapq.heappush(pq, (cost + grid[nx][ny], nx, ny))
      
        return False

This approach guarantees that when we visit a cell for the first time, we've found the minimum cost path to it, eliminating redundant processing.