Watch 6 video solutions for Escape the Spreading Fire, a hard level problem involving Array, Binary Search, Breadth-First Search. This walkthrough by Programming Live with Larry has 2,853 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
0 represents grass,1 represents fire,2 represents 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 either 0, 1, or 2.grid[0][0] == grid[m - 1][n - 1] == 0Problem 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 | 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 |