Escape the Spreading Fire - Solution & Explanation
Problem Statement
You are given a 0-indexed 2D integer array grid of size m x n which represents a field. Each cell has one of three values:
0represents grass,1represents fire,2represents a wall that you and fire cannot pass through.
You are situated in the top-left cell, (0, 0), and you want to travel to the safehouse at the bottom-right cell, (m - 1, n - 1). Every minute, you may move to an adjacent grass cell. After your move, every fire cell will spread to all adjacent cells that are not walls.
Return the maximum number of minutes that you can stay in your initial position before moving while still safely reaching the safehouse. If this is impossible, return -1. If you can always reach the safehouse regardless of the minutes stayed, return 109.
Note that even if the fire spreads to the safehouse immediately after you have reached it, it will be counted as safely reaching the safehouse.
A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).
Example 1:
Input: 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]] Output: 3 Explanation: The figure above shows the scenario where you stay in the initial position for 3 minutes. You will still be able to safely reach the safehouse. Staying for more than 3 minutes will not allow you to safely reach the safehouse.
Example 2:
Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]] Output: -1 Explanation: The figure above shows the scenario where you immediately move towards the safehouse. Fire will spread to any cell you move towards and it is impossible to safely reach the safehouse. Thus, -1 is returned.
Example 3:
Input: grid = [[0,0,0],[2,2,0],[1,2,0]] Output: 1000000000 Explanation: The figure above shows the initial grid. Notice that the fire is contained by walls and you will always be able to safely reach the safehouse. Thus, 109 is returned.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 3004 <= m * n <= 2 * 104grid[i][j]is either0,1, or2.grid[0][0] == grid[m - 1][n - 1] == 0
Approach Overview
Problem Overview: You are given a grid where some cells contain fire. Every minute, the fire spreads to adjacent cells. Starting from the top-left cell, you want to reach the safehouse at the bottom-right cell without being caught by the fire. The goal is to compute the maximum number of minutes you can wait before starting your movement while still guaranteeing a safe escape.
Approach 1: Simultaneous Breadth-First Search for Fire and Player (O(m*n))
This approach runs two Breadth-First Search traversals simultaneously. One BFS expands all fire sources and tracks which cells burn each minute. Another BFS simulates the player's movement from the start cell. At each step, you compare arrival times: the player can only enter a cell if the fire reaches it strictly later. The grid behaves like a time-layered graph where each minute represents a new BFS layer. Time complexity is O(m*n) because every cell is processed a constant number of times, and space complexity is also O(m*n) for queues and visitation tracking.
Approach 2: Binary Search on Waiting Time with Simulation (O(m*n log(m*n)))
The key observation is monotonicity: if you can escape after waiting t minutes, you can also escape after waiting any time less than t. That property allows a Binary Search over the waiting time. For each candidate wait value, simulate the fire spread for t minutes and then run BFS to check whether the player can still reach the safehouse. The search space ranges from 0 to roughly m*n. Each feasibility check performs BFS across the grid, giving O(m*n) per check and O(m*n log(m*n)) total time with O(m*n) space.
Approach 3: Binary Search + Precomputed Fire Times (Optimal in Practice)
A more structured solution first computes the earliest time the fire reaches every cell using multi-source BFS from all fire locations. Store these values in a matrix. Then binary search the maximum waiting time. During each feasibility check, run BFS from the start cell and ensure the player reaches each cell strictly before its fire arrival time (except the safehouse where equal time may still be valid depending on the rule). This separates the fire simulation from the player traversal and avoids recomputing fire spread repeatedly. Time complexity remains O(m*n log(m*n)), while space complexity is O(m*n). The grid operations rely heavily on matrix traversal and queue-based BFS.
Recommended for interviews: Binary Search combined with BFS is the most expected solution. Interviewers want to see recognition of the monotonic property (which suggests binary search) and the use of BFS to compute shortest arrival times in a grid. A brute simulation or simultaneous BFS shows understanding of grid traversal, but the binary search formulation demonstrates stronger algorithmic reasoning.
Approach 1: Simultaneous Breadth-First Search (BFS) for Fire and Player
This approach involves using a BFS strategy to simulate the spread of fire and movement of the player simultaneously. We utilize two separate BFS traversals: one for the player starting from (0,0) and another for the fire spreading from initially burning cells. The goal is to find the longest possible delay before starting the player’s movement that allows the player to reach the safehouse (m-1, n-1) before or simultaneously as the fire reaches.
This solution uses two BFS traversals. The first traversal calculates the time each cell will be reached by fire, and the second calculates how the player can move through the grid. By comparing the fire's arrival time at the bottom-right corner with the player's, we determine the maximum time the player can wait at the start. If the player can always reach before or simultaneously with the fire, the solution is 109.
Code
Python
JavaScript
Complexity
Time Complexity: O(m * n), where m and n are the dimensions of the grid, because each BFS runs through the entire grid.
Space Complexity: O(m * n), primarily for the storage of the time arrays and queues.
Approach 2: Binary Search on Waiting Time with Simulation
This approach modifies the typical BFS traversal by incorporating a binary search to efficiently determine the maximum waiting time at the start. We define a range of possible initial waiting times and validate each candidate time by simulating the player's and fire’s movements through sequential iterations of BFS-inspired traversal.
This C solution leverages binary search to optimize waiting time at the start point. BFS is used to simulate and check the possibility of reaching the destination safely after waiting indicated by a binary search candidate. The logic integrates optimizing the search space for waiting time, providing an efficient solution strategy.
Complexity
Time Complexity: O(m * n * log(T)), where T is the upper bound for waiting time.
Space Complexity: O(m * n) for storage of simulation states.
Approach 3: Binary Search + BFS
We notice that if a stay time t satisfies the condition, then all stay times less than t also satisfy the condition. Therefore, we can consider using binary search to find the maximum stay time that satisfies the condition.
We define the left boundary of binary search as l=-1 and the right boundary as r=m times n. In each iteration of binary search, we take the midpoint mid of l and r as the current stay time and check if it satisfies the condition. If it does, we update l to mid, otherwise we update r to mid-1. Finally, if l=m times n, it means there is no stay time that satisfies the condition, so we return 10^9, otherwise we return l.
The key problem is how to determine whether a stay time t satisfies the condition. We can use breadth-first search to simulate the spread of fire within t time. If the fire spreads to the starting position after staying for t time, it means the condition is not satisfied and we return early. Otherwise, we use breadth-first search again, searching in four directions from the current position each time, and after each round, we need to spread the fire in four directions. If we find a path from the starting position to the ending position during this process, it means the condition is satisfied.
The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the grid, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simultaneous Breadth-First Search (BFS) for Fire and Player | Time Complexity: O(m * n), where m and n are the dimensions of the grid, because each BFS runs through the entire grid. Space Complexity: O(m * n), primarily for the storage of the time arrays and queues. |
| Binary Search on Waiting Time with Simulation | Time Complexity: O(m * n * log(T)), where T is the upper bound for waiting time. Space Complexity: O(m * n) for storage of simulation states. |
| Binary Search + BFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simultaneous BFS for Fire and Player | O(m*n) | O(m*n) | Direct simulation when modeling both movements together is easier to reason about |
| Binary Search with Full Simulation | O(m*n log(m*n)) | O(m*n) | When the feasibility of escape is monotonic with respect to waiting time |
| Binary Search + Precomputed Fire BFS | O(m*n log(m*n)) | O(m*n) | Most common optimized approach; avoids recomputing fire spread for every check |
Video Solution
2258. Escape the Spreading Fire (Leetcode Hard) • Programming Live with Larry • 3,003 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Escape the Spreading Fire easy or hard?
Escape the Spreading Fire Python/Java solution
What is the best approach for Escape the Spreading Fire?
Is Escape the Spreading Fire asked at Google/Amazon/Meta?
What data structure is used in Escape the Spreading Fire?
What is the time complexity of Escape the Spreading Fire?
How to solve Escape the Spreading Fire in O(m*n log(m*n))?
Ready to solve this problem?
Practice Escape the Spreading Fire with our built-in code editor and test cases.
Practice on FleetCode