LeetCode 2258 - Escape the Spreading Fire

This problem asks us to determine how long we can safely wait before starting to move from the top-left corner of a grid to the bottom-right corner while a fire spreads across the grid over time.

leetcodehardarraybinary-searchbreadth-first-searchmatrix

LeetCode Problem 2258

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem asks us to determine how long we can safely wait before starting to move from the top-left corner of a grid to the bottom-right corner while a fire spreads across the grid over time.

The grid contains three types of cells:

  • 0 represents empty grass that both the player and the fire may move through.
  • 1 represents a fire source.
  • 2 represents a wall that blocks both movement and fire spread.

The player begins at (0, 0) and wants to reach the safehouse at (m - 1, n - 1).

The sequence of events for every minute is extremely important:

  1. The player moves first.
  2. After the move, the fire spreads to adjacent cells.

The fire spreads in four directions, up, down, left, and right, exactly like a standard breadth-first search expansion.

The goal is to compute the maximum number of minutes the player may remain standing still at the starting cell before beginning movement, while still being able to reach the safehouse safely.

There are three possible outcomes:

  • Return -1 if escape is impossible even when starting immediately.
  • Return 10^9 if escape is always possible regardless of waiting time.
  • Otherwise, return the largest valid waiting time.

One subtle but extremely important rule is that arriving at the safehouse at the exact same time the fire reaches it is still considered safe. This exception applies only to the destination cell. For all other cells, the player must arrive strictly before the fire.

The constraints are large:

  • m * n <= 2 * 10^4

This immediately tells us that expensive repeated simulations over the entire grid could become problematic. We need something close to linear or near-linear complexity per major operation.

Several edge cases are especially important:

  • The fire may already block all paths immediately.
  • The fire may be completely trapped by walls.
  • The player and fire may reach cells simultaneously.
  • The safehouse allows equal arrival time, but intermediate cells do not.
  • The starting cell itself may eventually catch fire before movement begins.

A naive implementation often fails because it mishandles timing comparisons or forgets the special rule for the destination cell.

Approaches

Brute Force Approach

The most straightforward solution is to try every possible waiting time one by one.

For a chosen waiting time t:

  1. Simulate the fire spreading for t minutes.
  2. Start a BFS for the player.
  3. At every minute:
  • Move the player.
  • Spread the fire.
  1. Check whether the player reaches the safehouse safely.

This approach is conceptually simple because it directly follows the problem statement. Unfortunately, it is far too slow.

The maximum useful waiting time can be very large, potentially up to 10^9. Even if we cap the search at some practical limit based on grid size, repeatedly simulating both fire and player movement becomes extremely expensive.

The major inefficiency is recomputing the fire spread from scratch for every tested waiting time.

Key Insight

The crucial optimization is to precompute the earliest time the fire reaches every cell.

This transforms the problem from a dynamic simulation into a timing comparison problem.

We can perform a multi-source BFS starting from every fire cell simultaneously. This gives us:

  • fire_time[r][c] = earliest minute fire reaches cell

Once we know fire arrival times, we can test whether a particular waiting time is feasible using another BFS for the player.

During the player's BFS:

  • For intermediate cells:

  • player arrival time must be strictly less than fire arrival time

  • For the destination:

  • player arrival time may be less than or equal to fire arrival time

Now we can binary search the answer because feasibility is monotonic:

  • If waiting x minutes works, then all smaller waiting times also work.
  • If waiting x minutes fails, then all larger waiting times also fail.

This converts the problem into:

  • One BFS for fire preprocessing
  • Multiple BFS checks during binary search

This is efficient enough for the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O((m × n)^2) or worse O(m × n) Repeatedly simulates fire and player movement
Optimal O(m × n × log(m × n)) O(m × n) Precompute fire times and binary search waiting time

Algorithm Walkthrough

  1. Precompute fire arrival times using multi-source BFS.

We create a matrix fire_time initialized to infinity. Every initial fire cell is inserted into the BFS queue with time 0.

Using BFS guarantees that the first time we visit a cell is the earliest possible time the fire can reach it. 2. Define a feasibility check function.

The function can_escape(wait) determines whether the player can survive after waiting wait minutes before moving. 3. Handle the starting cell carefully.

If the fire reaches (0, 0) before or exactly when the player starts moving, escape is impossible.

Since the player waits first, we require:

wait < fire_time[0][0]

unless the fire never reaches the start. 4. Run BFS for the player.

The player's initial time is wait.

For each move:

  • moving to a neighbor increases time by 1
  • walls cannot be entered
  • visited cells are skipped
  1. Compare player arrival time with fire arrival time.

For normal cells:

player_time < fire_time[cell]

For the safehouse:

player_time <= fire_time[safehouse]

This directly implements the special rule from the statement. 6. Return whether the safehouse is reachable.

If BFS reaches the destination under valid timing constraints, the waiting time is feasible. 7. Binary search the maximum valid waiting time.

Since feasibility is monotonic:

  • valid waits form a prefix
  • invalid waits form a suffix

We binary search over waiting times. 8. Handle the infinite-wait case.

If the maximum feasible wait is very large, specifically at least m * n, then the fire can never meaningfully block the player.

In this case, return:

10^9

Why it works

The fire BFS correctly computes the earliest possible fire arrival time for every reachable cell because BFS explores shortest paths in an unweighted grid.

The player BFS then checks whether the player can stay ahead of the fire along some path. Since every move costs exactly one minute, BFS again guarantees shortest arrival times.

Binary search is valid because waiting longer can never improve survivability. Once a waiting time becomes impossible, all larger waiting times are also impossible.

Together, these properties guarantee correctness.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        INF = 10**18
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        fire_time = [[INF] * cols for _ in range(rows)]
        queue = deque()

        # Multi-source BFS for fire
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    fire_time[r][c] = 0
                    queue.append((r, c))

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and grid[nr][nc] != 2
                    and fire_time[nr][nc] == INF
                ):
                    fire_time[nr][nc] = fire_time[r][c] + 1
                    queue.append((nr, nc))

        def can_escape(wait: int) -> bool:
            # Fire reaches start before or at departure
            if wait >= fire_time[0][0]:
                return False

            queue = deque([(0, 0, wait)])
            visited = [[False] * cols for _ in range(rows)]
            visited[0][0] = True

            while queue:
                r, c, time = queue.popleft()

                if r == rows - 1 and c == cols - 1:
                    return True

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc
                    next_time = time + 1

                    if not (0 <= nr < rows and 0 <= nc < cols):
                        continue

                    if grid[nr][nc] == 2 or visited[nr][nc]:
                        continue

                    fire_arrival = fire_time[nr][nc]

                    # Destination allows equal arrival
                    if nr == rows - 1 and nc == cols - 1:
                        if next_time > fire_arrival:
                            continue
                    else:
                        if next_time >= fire_arrival:
                            continue

                    visited[nr][nc] = True
                    queue.append((nr, nc, next_time))

            return False

        left = 0
        right = rows * cols + 1
        answer = -1

        while left <= right:
            mid = (left + right) // 2

            if can_escape(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        if answer == rows * cols + 1:
            return 10**9

        return answer

The implementation begins by computing the earliest fire arrival time for every cell. This is done using a multi-source BFS where all fire cells are inserted into the queue initially.

The fire_time matrix stores the minimum minute at which fire reaches each cell. Unreachable cells remain at infinity.

The helper function can_escape(wait) checks whether escape is possible after waiting wait minutes. It immediately rejects cases where the starting cell burns before movement begins.

The player's BFS tracks both position and current time. Every movement increases time by one minute.

The timing comparisons are the most important part of the implementation:

  • Intermediate cells require strict inequality.
  • The destination allows equality.

Finally, binary search determines the largest feasible waiting time efficiently.

Go Solution

package main

import "container/list"

func maximumMinutes(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	const INF int = 1_000_000_000

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	fireTime := make([][]int, rows)
	for i := range fireTime {
		fireTime[i] = make([]int, cols)
		for j := range fireTime[i] {
			fireTime[i][j] = INF
		}
	}

	type Node struct {
		r, c int
	}

	queue := list.New()

	// Multi-source BFS for fire
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 1 {
				fireTime[r][c] = 0
				queue.PushBack(Node{r, c})
			}
		}
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		cur := front.Value.(Node)

		for _, d := range directions {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				continue
			}

			if grid[nr][nc] == 2 {
				continue
			}

			if fireTime[nr][nc] != INF {
				continue
			}

			fireTime[nr][nc] = fireTime[cur.r][cur.c] + 1
			queue.PushBack(Node{nr, nc})
		}
	}

	canEscape := func(wait int) bool {
		if wait >= fireTime[0][0] {
			return false
		}

		type State struct {
			r, c, t int
		}

		visited := make([][]bool, rows)
		for i := range visited {
			visited[i] = make([]bool, cols)
		}

		queue := list.New()
		queue.PushBack(State{0, 0, wait})
		visited[0][0] = true

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			cur := front.Value.(State)

			if cur.r == rows-1 && cur.c == cols-1 {
				return true
			}

			for _, d := range directions {
				nr := cur.r + d[0]
				nc := cur.c + d[1]
				nt := cur.t + 1

				if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
					continue
				}

				if grid[nr][nc] == 2 || visited[nr][nc] {
					continue
				}

				fireArrival := fireTime[nr][nc]

				if nr == rows-1 && nc == cols-1 {
					if nt > fireArrival {
						continue
					}
				} else {
					if nt >= fireArrival {
						continue
					}
				}

				visited[nr][nc] = true
				queue.PushBack(State{nr, nc, nt})
			}
		}

		return false
	}

	left := 0
	right := rows*cols + 1
	answer := -1

	for left <= right {
		mid := (left + right) / 2

		if canEscape(mid) {
			answer = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	if answer == rows*cols+1 {
		return 1_000_000_000
	}

	return answer
}

The Go implementation closely mirrors the Python version, but there are several language-specific differences.

Go does not provide a built-in deque, so container/list is used for BFS queues.

Structs are used to represent BFS states cleanly. This avoids using nested slices or arrays for coordinates and timestamps.

The INF value is represented using a large integer constant instead of Python's arbitrary-precision integers.

Slices are initialized manually because Go does not support Python-style list comprehensions.

Worked Examples

Example 1

grid =
[
  [0,2,0,0,0,0,0],
  [0,0,0,2,2,1,0],
  [0,2,0,0,1,2,0],
  [0,0,2,2,2,0,2],
  [0,0,0,0,0,0,0]
]

Step 1: Compute fire arrival times

The fire starts from:

  • (1,5)
  • (2,4)

Multi-source BFS computes the earliest fire reach times.

A simplified view:

Cell Fire Arrival
(1,5) 0
(2,4) 0
nearby cells 1
farther cells increasing times

Walls remain unreachable.

Step 2: Binary search waiting time

Suppose we test wait = 3.

The player starts moving at time 3.

Step 3: Player BFS

The BFS explores paths while checking:

player_time < fire_time

for intermediate cells.

Eventually, the player reaches the destination before the fire closes all escape routes.

So wait = 3 succeeds.

Step 4: Test larger waits

Testing wait = 4 fails because the fire blocks critical cells before the player arrives.

Thus the answer is:

3

Example 2

grid =
[
  [0,0,0,0],
  [0,1,2,0],
  [0,2,0,0]
]

The fire expands rapidly into all possible paths.

Even with wait = 0, every route becomes unsafe before the player can reach the destination.

The BFS never reaches the safehouse.

Result:

-1

Example 3

grid =
[
  [0,0,0],
  [2,2,0],
  [1,2,0]
]

The fire is trapped behind walls.

The fire BFS cannot reach the path from start to destination.

Therefore, all path cells have infinite fire arrival time.

The player can wait arbitrarily long.

Result:

1000000000

Complexity Analysis

Measure Complexity Explanation
Time O(m × n × log(m × n)) One fire BFS plus binary search with BFS checks
Space O(m × n) Fire times, visited arrays, and BFS queues

The fire preprocessing BFS visits each cell at most once, giving O(m × n) complexity.

Each feasibility check also performs a BFS over the grid, again costing O(m × n).

Binary search performs O(log(m × n)) checks, so the total complexity becomes:

O(m × n × log(m × n))

This is efficient enough for grids containing up to 2 × 10^4 cells.

Test Cases

sol = Solution()

# Example 1
assert sol.maximumMinutes([
    [0,2,0,0,0,0,0],
    [0,0,0,2,2,1,0],
    [0,2,0,0,1,2,0],
    [0,0,2,2,2,0,2],
    [0,0,0,0,0,0,0]
]) == 3  # standard mixed scenario

# Example 2
assert sol.maximumMinutes([
    [0,0,0,0],
    [0,1,2,0],
    [0,2,0,0]
]) == -1  # impossible escape

# Example 3
assert sol.maximumMinutes([
    [0,0,0],
    [2,2,0],
    [1,2,0]
]) == 1000000000  # fire fully trapped

# Minimal grid with direct path
assert sol.maximumMinutes([
    [0,0],
    [0,0]
]) == 1000000000  # no fire anywhere

# Fire adjacent to start
assert sol.maximumMinutes([
    [0,1],
    [0,0]
]) == -1  # start immediately threatened

# Fire adjacent to destination
assert sol.maximumMinutes([
    [0,0,0],
    [0,0,1],
    [0,0,0]
]) >= 0  # validates destination timing logic

# Narrow corridor
assert sol.maximumMinutes([
    [0,2,0],
    [0,2,0],
    [0,0,0]
]) == 1000000000  # fire absent, constrained path

# Completely blocked route
assert sol.maximumMinutes([
    [0,2,0],
    [2,2,0],
    [0,0,0]
]) == -1  # no path exists

# Fire reaches destination exactly with player
assert sol.maximumMinutes([
    [0,0,0],
    [1,2,0],
    [0,0,0]
]) >= 0  # tests equal-arrival destination rule
Test Why
Example 1 Standard mixed fire and wall scenario
Example 2 Impossible escape case
Example 3 Infinite waiting scenario
Minimal grid Verifies behavior without fire
Fire adjacent to start Tests immediate danger
Fire adjacent to destination Tests safehouse timing
Narrow corridor Tests constrained movement
Completely blocked route Tests disconnected paths
Equal arrival at destination Verifies special safehouse rule

Edge Cases

Fire Never Reaches the Safehouse

One tricky scenario occurs when walls completely isolate the fire from the player's path. In this case, the fire BFS leaves many cells with infinite arrival time.

A buggy implementation might still impose artificial timing limits and incorrectly reject large waiting times.

This implementation handles the case correctly because unreachable fire times remain infinity, allowing the player BFS to move freely forever. When the binary search detects arbitrarily large feasible waits, the algorithm returns 10^9.

Player and Fire Reach Destination Simultaneously

The destination cell has a special rule:

player_time <= fire_time[destination]

Many incorrect solutions accidentally require strict inequality everywhere.

This implementation explicitly checks whether the current cell is the safehouse and applies the relaxed comparison only there.

Fire Reaches the Starting Cell Before Movement Begins

If the player waits too long, the starting cell itself may ignite before movement begins.

This is easy to overlook because many BFS implementations only check timing after movement starts.

This solution correctly rejects such waits immediately using:

if wait >= fire_time[0][0]:
    return False

That guarantees the player never begins from a burning cell.