2258. Escape the Spreading Fire

HardBreadth-First SearchArrayBinary SearchMatrix

Problem Description

You are given a 2D grid representing a field where:

0 represents grass cells you can walk on
1 represents fire cells that will spread
2 represents walls that block both you and fire

You start at the top-left corner (0, 0) and need to reach the safehouse at the bottom-right corner (m-1, n-1).

The game mechanics work as follows:

Initially, you can choose to stay at your starting position for some number of minutes
Each minute you stay, the fire spreads to all adjacent grass cells (not through walls)
Once you start moving, you can move to an adjacent grass cell each minute
After each of your moves, the fire spreads again to adjacent grass cells
You cannot move through fire or walls

The goal is to find the maximum number of minutes you can wait at the starting position before beginning your journey, while still being able to safely reach the safehouse.

Return values:

Return the maximum number of minutes you can wait if it's possible to reach the safehouse
Return -1 if it's impossible to reach the safehouse at all
Return 10^9 if you can wait indefinitely and still reach the safehouse

Note that reaching the safehouse counts as safe even if fire spreads to it immediately after you arrive there.

Adjacent cells are those directly north, east, south, or west (sharing a side).

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 problem involves a 2D grid where we need to find paths. Each cell can be considered a node, and adjacent cells form edges. We need to navigate from one position to another while avoiding obstacles (walls and fire).

Is it a tree?

No: The grid structure is not a tree. It's a graph where cells can have multiple paths between them and may contain cycles.

Is the problem related to directed acyclic graphs?

No: The grid allows movement in all four directions (when not blocked), so it's not a DAG and can have cycles.

Is the problem related to shortest paths?

Yes: We need to find if a path exists from start (0,0) to end (m-1,n-1) while considering the spreading fire. The problem involves finding the optimal path timing - specifically, we're looking for the path that allows maximum waiting time at the start.

Is the graph Weighted?

No: All movements between adjacent cells take the same amount of time (1 minute). The graph is unweighted.

BFS

Yes: Since we have an unweighted graph and need to explore paths level by level (simulating minute-by-minute progression), BFS is the appropriate choice.

Conclusion: The flowchart suggests using BFS for this problem. This makes sense because:

We need to simulate the fire spreading level by level (minute by minute)
We need to find if a path exists from start to end position
The graph is unweighted (each move takes 1 minute)
BFS naturally handles the simultaneous exploration needed for both fire spreading and player movement

The solution uses BFS twice in each check:

First BFS simulates fire spreading for the initial waiting time
Second BFS simulates the player's movement while simultaneously spreading fire after each move

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that this problem has a monotonic property: if we can safely reach the safehouse after waiting t minutes, then we can also reach it after waiting any time less than t. Why? Because less waiting time means the fire has spread less, giving us more safe paths to work with.

This monotonic property immediately suggests binary search on the answer. We can search for the maximum waiting time between 0 and m × n (the total number of cells, which is an upper bound since fire can't spread more than this).

For each candidate waiting time mid in our binary search, we need to check if it's possible to reach the safehouse. This check involves two phases:

Fire spreading phase: First, simulate the fire spreading for mid minutes while we wait at the starting position. We use BFS to spread fire level by level, where each level represents one minute.
Escape phase: After waiting, we start moving. Here's where it gets tricky - we need to simulate both our movement AND the fire continuing to spread simultaneously. We move one step per minute, and after each round of our movement, the fire spreads one more level.

The simulation works like this:

Use BFS for the player's movement, exploring all reachable cells at distance d before moving to distance d+1
After processing each distance level (one minute of player movement), spread the fire one more level
If we reach (m-1, n-1) before getting caught by fire, this waiting time works
If the fire blocks all paths or catches us, this waiting time doesn't work

Special cases to consider:

If we can wait m × n minutes and still escape, we can wait indefinitely (return 10^9)
If we can't escape even without waiting (when t = 0), return -1

The beauty of this approach is that binary search reduces our search space from O(m × n) possible waiting times to just O(log(m × n)) checks, and each check is done efficiently using BFS in O(m × n) time.

Learn more about Breadth-First Search and Binary Search patterns.

Solution Approach

The solution implements binary search combined with BFS simulation as outlined in the reference approach. Let's break down the implementation:

Binary Search Setup

We initialize the binary search bounds:

l = -1: The left boundary (minimum waiting time minus 1)
r = m * n: The right boundary (maximum possible waiting time)

The binary search loop continues while l < r, using the standard pattern:

mid = (l + r + 1) >> 1  # Calculate midpoint with upward rounding
if check(mid):
    l = mid  # If we can escape with mid minutes wait, try longer
else:
    r = mid - 1  # If we can't escape, try shorter wait

The Check Function

The check(t) function determines if we can reach the safehouse after waiting t minutes. It consists of two main phases:

Phase 1: Initial Fire Spreading

# Initialize fire grid and queue with all initial fire positions
fire = [[False] * n for _ in range(m)]
q1 = deque()
for i, row in enumerate(grid):
    for j, x in enumerate(row):
        if x == 1:  # Found fire
            fire[i][j] = True
            q1.append((i, j))

# Spread fire for t minutes while we wait
while t and q1:
    q1 = spread(q1)
    t -= 1

Phase 2: Simultaneous Movement and Fire Spreading

# Check if starting position is on fire
if fire[0][0]:
    return False

# BFS for player movement
q2 = deque([(0, 0)])
vis = [[False] * n for _ in range(m)]
vis[0][0] = True

while q2:
    # Process all cells at current distance (one minute of movement)
    for _ in range(len(q2)):
        i, j = q2.popleft()
        if fire[i][j]:  # Skip if current position caught fire
            continue
      
        # Try all 4 directions
        for a, b in pairwise(dirs):  # dirs = (-1, 0, 1, 0, -1)
            x, y = i + a, j + b
            if valid_move(x, y):  # Check bounds, not visited, not on fire, is grass
                if x == m - 1 and y == n - 1:  # Reached safehouse!
                    return True
                vis[x][y] = True
                q2.append((x, y))
  
    # After each round of movement, fire spreads one more level
    q1 = spread(q1)

The Spread Function

The spread function handles one minute of fire spreading using BFS:

def spread(q: Deque[int]) -> Deque[int]:
    nq = deque()  # New queue for next level
    while q:
        i, j = q.popleft()
        for a, b in pairwise(dirs):  # Check all 4 directions
            x, y = i + a, j + b
            if 0 <= x < m and 0 <= y < n and not fire[x][y] and grid[x][y] == 0:
                fire[x][y] = True  # Mark as on fire
                nq.append((x, y))  # Add to next level
    return nq

Direction Handling

The solution uses a clever pattern for iterating through 4 directions:

dirs = (-1, 0, 1, 0, -1)
pairwise(dirs) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
These represent movements: up, right, down, left

Final Result

After binary search completes:

If l == m * n: We can wait for the maximum time, return 10^9
Otherwise: Return l as the maximum waiting time

The time complexity is O(m * n * log(m * n)) where each binary search iteration runs a BFS simulation in O(m * n) time.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Consider a 3×3 grid:

0 0 0
0 1 0  
0 0 0

Where we start at (0,0) and need to reach (2,2). There's fire at (1,1).

Step 1: Binary Search Setup

Initialize: l = -1, r = 3 × 3 = 9
We'll binary search for the maximum waiting time

Step 2: First Binary Search Iteration

mid = (l + r + 1) / 2 = (-1 + 9 + 1) / 2 = 4
Check if we can escape after waiting 4 minutes

Checking wait time = 4:

Phase 1: Fire spreads for 4 minutes while we wait

Minute 0: Fire at (1,1)
Minute 1: Fire spreads to (0,1), (1,0), (1,2), (2,1)
```
0 1 0
1 1 1
0 1 0
```
Minute 2: Fire spreads to (0,0), (0,2), (2,0), (2,2)
```
1 1 1
1 1 1
1 1 1
```
Minutes 3-4: All cells already on fire

Phase 2: Try to escape

Starting position (0,0) is on fire → Cannot escape!
check(4) returns False
Update: r = mid - 1 = 3

Step 3: Second Binary Search Iteration

mid = (-1 + 3 + 1) / 2 = 1
Check if we can escape after waiting 1 minute

Checking wait time = 1:

Phase 1: Fire spreads for 1 minute

Initial: Fire at (1,1)
After 1 minute: Fire at (1,1), (0,1), (1,0), (1,2), (2,1)
```
0 1 0
1 1 1
0 1 0
```

Phase 2: Escape attempt

Start at (0,0) - not on fire ✓
Our movement minute by minute:

Minute 1 (our first move):
- From (0,0), we can move to (1,0) or (0,1)
- But both are on fire! Cannot move anywhere
- check(1) returns False
- Update: r = mid - 1 = 0

Step 4: Third Binary Search Iteration

mid = (-1 + 0 + 1) / 2 = 0
Check if we can escape without waiting

Checking wait time = 0:

Phase 1: No waiting (skip)

Phase 2: Immediate escape

Fire initially only at (1,1)
Our path simulation:

Minute 1:
- Player moves: (0,0) → can reach (1,0) or (0,1)
- Add both to queue
- Fire spreads: (1,1) → (0,1), (1,0), (1,2), (2,1)
Minute 2:
- Player moves from (0,1): blocked by fire
- Player moves from (1,0): blocked by fire
- Both positions caught by fire after minute 1
- No valid moves remain
check(0) returns False
Update: r = mid - 1 = -1

Step 5: Binary Search Completes

l = -1, r = -1, so l == r
Final answer: l = -1
Return -1 (impossible to reach safehouse)

Alternative Scenario: If the grid had been:

0 0 0
0 0 1  
0 0 0

With fire at (1,2) instead, we could find a path:

Without waiting: (0,0) → (0,1) → (0,2) → (1,2) would be blocked
But: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) works!
Binary search would find we can wait 0 minutes and still escape
If we could wait longer and still escape, binary search would find that maximum

This example shows how the algorithm combines binary search to find the optimal waiting time with BFS simulation to check if escape is possible for each candidate time.

Solution Implementation

1class Solution:
2    def maximumMinutes(self, grid: List[List[int]]) -> int:
3        def spread_fire(fire_queue: Deque[Tuple[int, int]]) -> Deque[Tuple[int, int]]:
4            """
5            Spread fire to adjacent cells for one time unit.
6            Returns a new queue with newly burning cells.
7            """
8            new_queue = deque()
9            while fire_queue:
10                row, col = fire_queue.popleft()
11                # Check all 4 adjacent cells (up, right, down, left)
12                for i in range(4):
13                    new_row = row + directions[i]
14                    new_col = col + directions[i + 1]
15                    # Check if the new position is valid and can catch fire
16                    if (0 <= new_row < rows and 
17                        0 <= new_col < cols and 
18                        not is_on_fire[new_row][new_col] and 
19                        grid[new_row][new_col] == 0):
20                        is_on_fire[new_row][new_col] = True
21                        new_queue.append((new_row, new_col))
22            return new_queue
23
24        def can_escape_with_delay(wait_time: int) -> bool:
25            """
26            Check if we can reach the safehouse starting after 'wait_time' minutes.
27            """
28            # Reset fire grid
29            for row in range(rows):
30                for col in range(cols):
31                    is_on_fire[row][col] = False
32          
33            # Initialize fire starting positions
34            fire_queue = deque()
35            for row in range(rows):
36                for col in range(cols):
37                    if grid[row][col] == 1:
38                        is_on_fire[row][col] = True
39                        fire_queue.append((row, col))
40          
41            # Let fire spread for 'wait_time' minutes before we start moving
42            remaining_time = wait_time
43            while remaining_time > 0 and fire_queue:
44                fire_queue = spread_fire(fire_queue)
45                remaining_time -= 1
46          
47            # If starting position is on fire, we can't escape
48            if is_on_fire[0][0]:
49                return False
50          
51            # BFS to find if we can reach the safehouse
52            person_queue = deque([(0, 0)])
53            visited = [[False] * cols for _ in range(rows)]
54            visited[0][0] = True
55          
56            while person_queue:
57                # Process all positions reachable in current minute
58                current_level_size = len(person_queue)
59                for _ in range(current_level_size):
60                    row, col = person_queue.popleft()
61                    # Skip if current position is on fire
62                    if is_on_fire[row][col]:
63                        continue
64                  
65                    # Try moving to adjacent cells
66                    for i in range(4):
67                        new_row = row + directions[i]
68                        new_col = col + directions[i + 1]
69                      
70                        if (0 <= new_row < rows and 
71                            0 <= new_col < cols and 
72                            not visited[new_row][new_col] and 
73                            not is_on_fire[new_row][new_col] and 
74                            grid[new_row][new_col] == 0):
75                            # Check if we reached the safehouse
76                            if new_row == rows - 1 and new_col == cols - 1:
77                                return True
78                            visited[new_row][new_col] = True
79                            person_queue.append((new_row, new_col))
80              
81                # Fire spreads after each minute of movement
82                fire_queue = spread_fire(fire_queue)
83          
84            return False
85
86        # Initialize grid dimensions
87        rows, cols = len(grid), len(grid[0])
88      
89        # Binary search bounds: -1 means we start immediately, rows*cols is upper bound
90        left, right = -1, rows * cols
91      
92        # Direction vectors for adjacent cells: up, right, down, left
93        directions = [-1, 0, 1, 0, -1]
94      
95        # Track which cells are on fire
96        is_on_fire = [[False] * cols for _ in range(rows)]
97      
98        # Binary search for maximum wait time
99        while left < right:
100            mid = (left + right + 1) >> 1  # Equivalent to (left + right + 1) // 2
101            if can_escape_with_delay(mid):
102                left = mid  # Can wait at least 'mid' minutes
103            else:
104                right = mid - 1  # Must wait less than 'mid' minutes
105      
106        # If we can wait for the maximum time, return 10^9 (forever)
107        return int(1e9) if left == rows * cols else left
108

1class Solution {
2    // Grid dimensions and data
3    private int[][] grid;
4    private boolean[][] fireSpread;  // Tracks cells on fire
5    private boolean[][] visited;      // Tracks visited cells by person
6    private final int[] directions = {-1, 0, 1, 0, -1};  // Direction vectors for 4-directional movement
7    private int rows;
8    private int cols;
9
10    /**
11     * Finds the maximum number of minutes to wait at start position before escaping.
12     * Uses binary search to find the maximum safe waiting time.
13     * 
14     * @param grid 2D array where 0=grass, 1=fire, 2=wall
15     * @return Maximum minutes to wait, or 1000000000 if can wait indefinitely
16     */
17    public int maximumMinutes(int[][] grid) {
18        rows = grid.length;
19        cols = grid[0].length;
20        this.grid = grid;
21        fireSpread = new boolean[rows][cols];
22        visited = new boolean[rows][cols];
23      
24        // Binary search on the waiting time
25        int left = -1;
26        int right = rows * cols;
27      
28        while (left < right) {
29            int mid = (left + right + 1) >> 1;  // Ceiling division
30            if (check(mid)) {
31                left = mid;  // Can wait at least mid minutes
32            } else {
33                right = mid - 1;  // Cannot wait mid minutes
34            }
35        }
36      
37        // If can wait for grid size time, can wait forever
38        return left == rows * cols ? 1000000000 : left;
39    }
40
41    /**
42     * Checks if person can reach the safehouse after waiting t minutes.
43     * Simulates fire spread for t minutes, then person movement with simultaneous fire spread.
44     * 
45     * @param waitTime Number of minutes to wait before starting
46     * @return true if person can reach bottom-right corner, false otherwise
47     */
48    private boolean check(int waitTime) {
49        // Reset fire and visited arrays
50        for (int i = 0; i < rows; ++i) {
51            Arrays.fill(fireSpread[i], false);
52            Arrays.fill(visited[i], false);
53        }
54      
55        // Initialize fire queue with all initial fire positions
56        Deque<int[]> fireQueue = new ArrayDeque<>();
57        for (int i = 0; i < rows; ++i) {
58            for (int j = 0; j < cols; ++j) {
59                if (grid[i][j] == 1) {
60                    fireQueue.offer(new int[] {i, j});
61                    fireSpread[i][j] = true;
62                }
63            }
64        }
65      
66        // Spread fire for waitTime minutes before person starts moving
67        for (; waitTime > 0 && !fireQueue.isEmpty(); --waitTime) {
68            fireQueue = spread(fireQueue);
69        }
70      
71        // If starting position is on fire, cannot escape
72        if (fireSpread[0][0]) {
73            return false;
74        }
75      
76        // Initialize person's BFS from top-left corner
77        Deque<int[]> personQueue = new ArrayDeque<>();
78        personQueue.offer(new int[] {0, 0});
79        visited[0][0] = true;
80      
81        // Simultaneous BFS: person moves, then fire spreads
82        for (; !personQueue.isEmpty(); fireQueue = spread(fireQueue)) {
83            // Process all positions person can reach in current minute
84            for (int size = personQueue.size(); size > 0; --size) {
85                int[] currentPos = personQueue.poll();
86              
87                // Skip if current position is on fire
88                if (fireSpread[currentPos[0]][currentPos[1]]) {
89                    continue;
90                }
91              
92                // Try moving in all 4 directions
93                for (int k = 0; k < 4; ++k) {
94                    int nextRow = currentPos[0] + directions[k];
95                    int nextCol = currentPos[1] + directions[k + 1];
96                  
97                    // Check if next position is valid and safe
98                    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols 
99                        && !fireSpread[nextRow][nextCol] && !visited[nextRow][nextCol]
100                        && grid[nextRow][nextCol] == 0) {
101                      
102                        // Check if reached destination (bottom-right corner)
103                        if (nextRow == rows - 1 && nextCol == cols - 1) {
104                            return true;
105                        }
106                      
107                        visited[nextRow][nextCol] = true;
108                        personQueue.offer(new int[] {nextRow, nextCol});
109                    }
110                }
111            }
112        }
113      
114        return false;
115    }
116
117    /**
118     * Spreads fire to adjacent grass cells for one minute.
119     * 
120     * @param currentFireQueue Current positions of fire
121     * @return New queue with fire positions after spreading
122     */
123    private Deque<int[]> spread(Deque<int[]> currentFireQueue) {
124        Deque<int[]> nextFireQueue = new ArrayDeque<>();
125      
126        while (!currentFireQueue.isEmpty()) {
127            int[] firePos = currentFireQueue.poll();
128          
129            // Spread fire in all 4 directions
130            for (int k = 0; k < 4; ++k) {
131                int nextRow = firePos[0] + directions[k];
132                int nextCol = firePos[1] + directions[k + 1];
133              
134                // Check if fire can spread to this cell (must be grass and not already on fire)
135                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols 
136                    && !fireSpread[nextRow][nextCol] && grid[nextRow][nextCol] == 0) {
137                  
138                    fireSpread[nextRow][nextCol] = true;
139                    nextFireQueue.offer(new int[] {nextRow, nextCol});
140                }
141            }
142        }
143      
144        return nextFireQueue;
145    }
146}
147

1class Solution {
2public:
3    int maximumMinutes(vector<vector<int>>& grid) {
4        int rows = grid.size(), cols = grid[0].size();
5      
6        // Direction vectors for 4-directional movement (up, right, down, left)
7        int directions[5] = {-1, 0, 1, 0, -1};
8      
9        // Lambda function to spread fire to adjacent cells
10        auto spreadFire = [&](queue<pair<int, int>>& fireQueue, vector<vector<bool>>& fireGrid) {
11            queue<pair<int, int>> nextQueue;
12          
13            while (!fireQueue.empty()) {
14                auto [row, col] = fireQueue.front();
15                fireQueue.pop();
16              
17                // Try spreading fire in all 4 directions
18                for (int k = 0; k < 4; ++k) {
19                    int newRow = row + directions[k];
20                    int newCol = col + directions[k + 1];
21                  
22                    // Check if new position is valid and can catch fire
23                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
24                        !fireGrid[newRow][newCol] && grid[newRow][newCol] == 0) {
25                        fireGrid[newRow][newCol] = true;
26                        nextQueue.emplace(newRow, newCol);
27                    }
28                }
29            }
30            return nextQueue;
31        };
32      
33        // Lambda function to check if we can escape with 'waitTime' minutes delay
34        auto canEscape = [&](int waitTime) {
35            vector<vector<bool>> visited(rows, vector<bool>(cols, false));
36            vector<vector<bool>> onFire(rows, vector<bool>(cols, false));
37          
38            // Initialize fire positions from grid
39            queue<pair<int, int>> fireQueue;
40            for (int i = 0; i < rows; ++i) {
41                for (int j = 0; j < cols; ++j) {
42                    if (grid[i][j] == 1) {
43                        fireQueue.emplace(i, j);
44                        onFire[i][j] = true;
45                    }
46                }
47            }
48          
49            // Spread fire for 'waitTime' minutes before we start moving
50            for (int t = 0; t < waitTime && !fireQueue.empty(); ++t) {
51                fireQueue = spreadFire(fireQueue, onFire);
52            }
53          
54            // If starting position is on fire, we can't escape
55            if (onFire[0][0]) {
56                return false;
57            }
58          
59            // BFS to find path from (0,0) to (rows-1, cols-1)
60            queue<pair<int, int>> personQueue;
61            personQueue.emplace(0, 0);
62            visited[0][0] = true;
63          
64            // Simulate person movement and fire spread simultaneously
65            while (!personQueue.empty()) {
66                // Process all positions reachable in current minute
67                int queueSize = personQueue.size();
68                for (int d = 0; d < queueSize; ++d) {
69                    auto [row, col] = personQueue.front();
70                    personQueue.pop();
71                  
72                    // Skip if current position is on fire
73                    if (onFire[row][col]) {
74                        continue;
75                    }
76                  
77                    // Try moving in all 4 directions
78                    for (int k = 0; k < 4; ++k) {
79                        int newRow = row + directions[k];
80                        int newCol = col + directions[k + 1];
81                      
82                        // Check if new position is valid and safe
83                        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
84                            !visited[newRow][newCol] && !onFire[newRow][newCol] && 
85                            grid[newRow][newCol] == 0) {
86                          
87                            // Check if we reached the destination
88                            if (newRow == rows - 1 && newCol == cols - 1) {
89                                return true;
90                            }
91                          
92                            visited[newRow][newCol] = true;
93                            personQueue.emplace(newRow, newCol);
94                        }
95                    }
96                }
97              
98                // Spread fire after person moves
99                fireQueue = spreadFire(fireQueue, onFire);
100            }
101          
102            return false;
103        };
104      
105        // Binary search for maximum wait time
106        int left = -1, right = rows * cols;
107      
108        while (left < right) {
109            int mid = (left + right + 1) / 2;
110          
111            if (canEscape(mid)) {
112                left = mid;  // Can wait at least 'mid' minutes
113            } else {
114                right = mid - 1;  // Must wait less than 'mid' minutes
115            }
116        }
117      
118        // If we can wait for rows*cols minutes, we can wait forever (return 10^9)
119        return left == rows * cols ? 1000000000 : left;
120    }
121};
122

1/**
2 * Finds the maximum number of minutes you can wait before starting to escape from fire
3 * @param grid - 2D grid where 0 is empty, 1 is fire, 2 is wall
4 * @returns Maximum minutes to wait, or 1e9 if you can wait indefinitely
5 */
6function maximumMinutes(grid: number[][]): number {
7    const rows = grid.length;
8    const cols = grid[0].length;
9  
10    // Track fire spread positions
11    const fireSpread = Array.from({ length: rows }, () => 
12        Array.from({ length: cols }, () => false)
13    );
14  
15    // Track visited positions for person's movement
16    const visited = Array.from({ length: rows }, () => 
17        Array.from({ length: cols }, () => false)
18    );
19  
20    // Direction vectors for 4-directional movement (up, right, down, left)
21    const directions: number[] = [-1, 0, 1, 0, -1];
22  
23    // Binary search bounds for the waiting time
24    let left = -1;
25    let right = rows * cols;
26  
27    /**
28     * Spreads fire to adjacent cells for one time unit
29     * @param fireQueue - Current positions of fire fronts
30     * @returns New fire front positions after spreading
31     */
32    const spreadFire = (fireQueue: number[][]): number[][] => {
33        const nextQueue: number[][] = [];
34      
35        while (fireQueue.length > 0) {
36            const [row, col] = fireQueue.shift()!;
37          
38            // Check all 4 directions
39            for (let dir = 0; dir < 4; dir++) {
40                const newRow = row + directions[dir];
41                const newCol = col + directions[dir + 1];
42              
43                // Spread fire if within bounds, not already on fire, and is empty cell
44                if (newRow >= 0 && newRow < rows && 
45                    newCol >= 0 && newCol < cols && 
46                    !fireSpread[newRow][newCol] && 
47                    grid[newRow][newCol] === 0) {
48                  
49                    fireSpread[newRow][newCol] = true;
50                    nextQueue.push([newRow, newCol]);
51                }
52            }
53        }
54      
55        return nextQueue;
56    };
57  
58    /**
59     * Checks if person can reach bottom-right corner after waiting waitTime minutes
60     * @param waitTime - Number of minutes to wait before starting
61     * @returns true if person can reach destination, false otherwise
62     */
63    const canReachDestination = (waitTime: number): boolean => {
64        // Reset fire and visited arrays
65        for (let i = 0; i < rows; i++) {
66            fireSpread[i].fill(false);
67            visited[i].fill(false);
68        }
69      
70        // Initialize fire positions from grid
71        let fireQueue: number[][] = [];
72        for (let i = 0; i < rows; i++) {
73            for (let j = 0; j < cols; j++) {
74                if (grid[i][j] === 1) {
75                    fireQueue.push([i, j]);
76                    fireSpread[i][j] = true;
77                }
78            }
79        }
80      
81        // Spread fire for waitTime minutes
82        for (let time = waitTime; time > 0 && fireQueue.length > 0; time--) {
83            fireQueue = spreadFire(fireQueue);
84        }
85      
86        // If starting position is on fire, cannot escape
87        if (fireSpread[0][0]) {
88            return false;
89        }
90      
91        // BFS for person's movement starting from top-left
92        const personQueue: number[][] = [[0, 0]];
93        visited[0][0] = true;
94      
95        // Simultaneous BFS: person moves and fire spreads each minute
96        while (personQueue.length > 0) {
97            // Process all positions person can reach in current minute
98            const currentLevelSize = personQueue.length;
99          
100            for (let level = currentLevelSize; level > 0; level--) {
101                const [currentRow, currentCol] = personQueue.shift()!;
102              
103                // Skip if current position is on fire
104                if (fireSpread[currentRow][currentCol]) {
105                    continue;
106                }
107              
108                // Try moving in all 4 directions
109                for (let dir = 0; dir < 4; dir++) {
110                    const nextRow = currentRow + directions[dir];
111                    const nextCol = currentCol + directions[dir + 1];
112                  
113                    // Check if next position is valid and safe
114                    if (nextRow >= 0 && nextRow < rows &&
115                        nextCol >= 0 && nextCol < cols &&
116                        !visited[nextRow][nextCol] &&
117                        !fireSpread[nextRow][nextCol] &&
118                        grid[nextRow][nextCol] === 0) {
119                      
120                        // Check if reached destination
121                        if (nextRow === rows - 1 && nextCol === cols - 1) {
122                            return true;
123                        }
124                      
125                        visited[nextRow][nextCol] = true;
126                        personQueue.push([nextRow, nextCol]);
127                    }
128                }
129            }
130          
131            // Spread fire after person's movement
132            fireQueue = spreadFire(fireQueue);
133        }
134      
135        return false;
136    };
137  
138    // Binary search for maximum waiting time
139    while (left < right) {
140        const mid = (left + right + 1) >> 1;
141      
142        if (canReachDestination(mid)) {
143            left = mid;  // Can wait at least mid minutes
144        } else {
145            right = mid - 1;  // Cannot wait mid minutes
146        }
147    }
148  
149    // If can wait for grid size time, can wait indefinitely
150    return left === rows * cols ? 1e9 : left;
151}
152

Time and Space Complexity

Time Complexity: O(m × n × log(m × n))

The algorithm uses binary search on the range [-1, m × n], which requires O(log(m × n)) iterations. For each binary search iteration, the check function is called.

Within the check function:

Initial fire spreading for t minutes: Each spread operation processes at most O(m × n) cells, and we do this at most t times where t ≤ m × n, giving O(m × n) time.
BFS for the person's movement: The person's BFS visits each cell at most once, taking O(m × n) time.
Fire spreading during person's movement: The fire also spreads while the person moves, visiting each cell at most once throughout the entire process, contributing O(m × n) time.
Grid initialization and copying: O(m × n) for initializing the fire and vis arrays.

Therefore, each check function call takes O(m × n) time, and with O(log(m × n)) binary search iterations, the total time complexity is O(m × n × log(m × n)).

Space Complexity: O(m × n)

The algorithm uses:

fire array: O(m × n) space to track cells on fire
vis array: O(m × n) space to track visited cells during BFS
Two deques q1 and q2: In the worst case, these can contain O(m × n) elements
Recursive stack space: The algorithm is iterative, so no additional stack space is needed

The dominant space usage is O(m × n) from the 2D arrays and queues.

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

Common Pitfalls

1. Incorrect Handling of the Safehouse Arrival Condition

One of the most common mistakes is incorrectly handling when the player reaches the safehouse at the same time fire spreads to it. The problem states that "reaching the safehouse counts as safe even if fire spreads to it immediately after you arrive there."

Pitfall Code:

# WRONG: Checking if safehouse is on fire before attempting to reach it
if is_on_fire[rows - 1][cols - 1]:
    return False  # This prevents us from reaching safehouse even if we arrive at the same time

# Processing movement...
if new_row == rows - 1 and new_col == cols - 1:
    return True

Correct Approach:

# Check for safehouse DURING movement processing, not before
for i in range(4):
    new_row = row + directions[i]
    new_col = col + directions[i + 1]
  
    if (0 <= new_row < rows and 
        0 <= new_col < cols and 
        not visited[new_row][new_col] and 
        not is_on_fire[new_row][new_col] and  # Fire hasn't reached here YET
        grid[new_row][new_col] == 0):
      
        # Check safehouse immediately after confirming we can move there
        if new_row == rows - 1 and new_col == cols - 1:
            return True  # Safe arrival even if fire spreads here next

2. Fire Spreading Order Within BFS

Another critical pitfall is spreading fire at the wrong time relative to player movement. Fire should spread AFTER each complete round of player movements, not before or during.

Pitfall Code:

while person_queue:
    # WRONG: Spreading fire before processing movements
    fire_queue = spread_fire(fire_queue)
  
    for _ in range(len(person_queue)):
        row, col = person_queue.popleft()
        # Process movement...

Correct Approach:

while person_queue:
    current_level_size = len(person_queue)
  
    # Process ALL movements at current distance first
    for _ in range(current_level_size):
        row, col = person_queue.popleft()
        # Process movement...
  
    # Fire spreads AFTER all movements in this minute complete
    fire_queue = spread_fire(fire_queue)

3. Binary Search Boundary Initialization

A subtle but important pitfall is incorrectly initializing the binary search boundaries, particularly when no waiting is possible.

Pitfall Code:

# WRONG: Starting from 0 misses the case where we can't wait at all
left, right = 0, rows * cols

# This would return 0 when we should return -1 for impossible cases

Correct Approach:

# Start from -1 to handle the case where immediate movement is required
left, right = -1, rows * cols

# This allows the binary search to correctly identify:
# - Return -1 when impossible (left stays at -1)
# - Return 0 when we must move immediately but can escape
# - Return positive values for actual waiting times

4. Resetting State Between Binary Search Iterations

Failing to properly reset the fire state between different binary search attempts can lead to incorrect results.

Pitfall Code:

# WRONG: Using a global fire state that persists between checks
is_on_fire = [[False] * cols for _ in range(rows)]  # Defined once

def can_escape_with_delay(wait_time):
    # Forgetting to reset is_on_fire
    # Previous fire positions contaminate new simulation

Correct Approach:

def can_escape_with_delay(wait_time):
    # Reset fire grid at the start of each check
    for row in range(rows):
        for col in range(cols):
            is_on_fire[row][col] = False
  
    # Then initialize with original fire positions
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                is_on_fire[row][col] = True
                fire_queue.append((row, col))

5. Edge Case: Starting Position Already Has Fire

Not checking if the starting position (0, 0) initially contains fire or a wall.

Solution Enhancement:

# Add this check at the beginning of the main function
if grid[0][0] != 0 or grid[rows-1][cols-1] != 0:
    return -1  # Starting position or safehouse is not grass

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know

2258. Escape the Spreading Fire

Problem Description

Flowchart Walkthrough

Intuition

Solution Approach

Binary Search Setup

The Check Function

The Spread Function

Direction Handling

Final Result

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Incorrect Handling of the Safehouse Arrival Condition

2. Fire Spreading Order Within BFS

3. Binary Search Boundary Initialization

4. Resetting State Between Binary Search Iterations

5. Edge Case: Starting Position Already Has Fire

Recommended Readings