Escape the Spreading Fire

Hard

#2056Time: O((M*N)^2), where M and N are the dimensions of the grid. The `fireTime` calculation takes O(M*N). The main loop runs up to M*N times, and each iteration calls `canReach`, which also takes O(M*N) in the worst case.Space: O(M*N) to store the `fireTime` grid, the visited array, and the queue for BFS.

Algorithms

Binary Search Breadth-First Search

Data structures

Array Matrix

Prompt

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 10⁹.

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.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 10⁴
grid[i][j] is either 0, 1, or 2.
grid[0][0] == grid[m - 1][n - 1] == 0

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but less efficient approach is to check every possible wait time W linearly. We can start from a reasonable maximum possible wait time and go down to zero. The first value of W for which we can find a safe path to the safehouse is our answer.

Algorithm

First, pre-calculate the minimum time for fire to reach every grass cell. This is done using a multi-source BFS starting from all initial fire cells. Store these times in a fireTime grid.
Define a helper function canReach(W) that takes an integer W (wait time) and returns true if the safehouse is reachable, false otherwise.
The canReach(W) function works as follows:

It performs a BFS starting from (0, 0) to find a path for the person.
The initial time for the person's BFS is W.
A move to an adjacent cell (r, c) is valid only if the person's arrival time at that cell is strictly less than fireTime[r][c]. This ensures the person can move through the cell before it catches fire.
For the destination cell (m-1, n-1), the arrival time can be less than or equal to fireTime[m-1][n-1].

Check if canReach(m*n) is true. If so, it means a path immune to fire exists, and the answer is 10^9.
If not, iterate W from m*n - 1 down to 0. The first W for which canReach(W) returns true is the maximum wait time.
If the loop completes without finding a solution, return -1.

Walkthrough

The core of this approach relies on a helper function, canReach(W), which determines if it's possible to reach the safehouse given an initial wait time of W minutes.

First, we need to know when the fire reaches each cell. This can be pre-calculated using a multi-source Breadth-First Search (BFS) starting from all initial fire cells. Let's store these times in a fireTime grid. fireTime[r][c] will be the number of minutes it takes for fire to reach cell (r, c).

With the fireTime grid, the canReach(W) function can be implemented using another BFS, this time for the player's path. The player starts at (0, 0) at time W. A path is valid if for every cell (r, c) on the path, the player's arrival time is less than the fire's arrival time (fireTime[r][c]). For the final destination, the arrival times can be equal.

The main algorithm then iterates W from a maximum possible value (e.g., m * n) down to 0. For each W, it calls canReach(W). The first W that returns true is the maximum possible wait time.

Special cases to handle:

If canReach(m*n) is true, it implies a fire-proof path exists, so we can wait indefinitely. We return 10^9.
If the loop finishes without finding a valid W, it's impossible to reach the safehouse, so we return -1.

1class Solution {2    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};3    int m, n;4 5    public int maximumMinutes(int[][] grid) {6        m = grid.length;7        n = grid[0].length;8 9        int[][] fireTime = new int[m][n];10        for (int[] row : fireTime) {11            java.util.Arrays.fill(row, Integer.MAX_VALUE);12        }13        calculateFireTime(grid, fireTime);14 15        if (canReach(grid, fireTime, m * n)) {16            return 1_000_000_000;17        }18 19        for (int w = m * n - 1; w >= 0; w--) {20            if (canReach(grid, fireTime, w)) {21                return w;22            }23        }24 25        return -1;26    }27 28    private void calculateFireTime(int[][] grid, int[][] fireTime) {29        java.util.Queue<int[]> q = new java.util.LinkedList<>();30        for (int i = 0; i < m; i++) {31            for (int j = 0; j < n; j++) {32                if (grid[i][j] == 1) {33                    q.offer(new int[]{i, j});34                    fireTime[i][j] = 0;35                }36            }37        }38        int time = 0;39        while (!q.isEmpty()) {40            int size = q.size();41            time++;42            for (int i = 0; i < size; i++) {43                int[] curr = q.poll();44                for (int[] dir : dirs) {45                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];46                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && fireTime[nr][nc] == Integer.MAX_VALUE) {47                        fireTime[nr][nc] = time;48                        q.offer(new int[]{nr, nc});49                    }50                }51            }52        }53    }54 55    private boolean canReach(int[][] grid, int[][] fireTime, int waitTime) {56        if (waitTime >= fireTime[0][0]) return false;57 58        java.util.Queue<int[]> q = new java.util.LinkedList<>();59        q.offer(new int[]{0, 0});60        boolean[][] visited = new boolean[m][n];61        visited[0][0] = true;62 63        int time = waitTime;64        while (!q.isEmpty()) {65            int size = q.size();66            time++;67            for (int i = 0; i < size; i++) {68                int[] curr = q.poll();69                for (int[] dir : dirs) {70                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];71                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {72                        if (nr == m - 1 && nc == n - 1) {73                            if (time <= fireTime[nr][nc]) return true;74                        }75                        if (time < fireTime[nr][nc]) {76                            visited[nr][nc] = true;77                            q.offer(new int[]{nr, nc});78                        }79                    }80                }81            }82        }83        return false;84    }85}

Complexity

Time

O((M*N)^2), where M and N are the dimensions of the grid. The `fireTime` calculation takes O(M*N). The main loop runs up to M*N times, and each iteration calls `canReach`, which also takes O(M*N) in the worst case.

Space

O(M*N) to store the `fireTime` grid, the visited array, and the queue for BFS.

Trade-offs

Pros

Conceptually simple and easy to understand.
The logic for checking reachability is reusable in more optimal solutions.

Cons

The time complexity is high, making it likely to result in a 'Time Limit Exceeded' error on larger test cases.

A more efficient approach leverages the monotonic nature of the problem. If we can safely reach the safehouse by waiting W minutes, we can also do so by waiting any amount of time less than W. This property allows us to use binary search on the wait time W to find the maximum possible value.

Algorithm

First, pre-calculate the fireTime grid using a multi-source BFS, identical to the linear scan approach.
Recognize that the problem has a monotonic property: if waiting W minutes is safe, waiting W-1 minutes is also safe. This allows for binary search on the answer.
Set a search range for the wait time W, for example, from 0 to m*n.
Initialize low = 0, high = m*n, and ans = -1.
In a loop while low <= high:

Calculate mid = low + (high - low) / 2.
Use the canReach(mid) function to check if it's possible to reach the safehouse with a wait time of mid.
If canReach(mid) is true, mid is a possible answer. We try for a larger wait time, so we set ans = mid and low = mid + 1.
If canReach(mid) is false, mid is too long. We must wait less, so we set high = mid - 1.

After the loop, if ans equals the initial upper bound (m*n), it implies we can wait indefinitely, so return 10^9.
Otherwise, return ans. This will be the maximum valid wait time, or -1 if no solution exists.

Walkthrough

The overall structure is similar to the linear scan, but instead of checking every W, we use binary search to find the optimal W much faster.

The search space for W will be from 0 to a safe upper bound, like m * n.

Pre-computation: Just like the previous approach, we first compute the fireTime grid using a multi-source BFS from all fire sources.
Binary Search: We perform a binary search on the wait time W in the range [0, m*n]. For each mid value (our candidate W), we call the same canReach(mid) function to check if a safe path exists.
- If canReach(mid) is true, it means mid is a possible wait time. We try for a longer wait time by setting low = mid + 1 and storing mid as a potential answer.
- If canReach(mid) is false, the wait time mid is too long. We need to search for a smaller W by setting high = mid - 1.
Result: After the binary search loop terminates, the stored answer will be the maximum valid wait time. We then handle the special cases: if the answer is m*n, we return 10^9; otherwise, we return the answer (which could be -1 if no path was ever found).

1class Solution {2    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};3    int m, n;4 5    public int maximumMinutes(int[][] grid) {6        m = grid.length;7        n = grid[0].length;8 9        int[][] fireTime = new int[m][n];10        for (int[] row : fireTime) {11            java.util.Arrays.fill(row, Integer.MAX_VALUE);12        }13        calculateFireTime(grid, fireTime);14 15        int low = 0, high = m * n;16        int ans = -1;17        while (low <= high) {18            int mid = low + (high - low) / 2;19            if (canReach(grid, fireTime, mid)) {20                ans = mid;21                low = mid + 1;22            } else {23                high = mid - 1;24            }25        }26 27        return ans == m * n ? 1_000_000_000 : ans;28    }29 30    // The calculateFireTime and canReach methods are identical to the previous approach.31    private void calculateFireTime(int[][] grid, int[][] fireTime) {32        java.util.Queue<int[]> q = new java.util.LinkedList<>();33        for (int i = 0; i < m; i++) {34            for (int j = 0; j < n; j++) {35                if (grid[i][j] == 1) {36                    q.offer(new int[]{i, j});37                    fireTime[i][j] = 0;38                }39            }40        }41        int time = 0;42        while (!q.isEmpty()) {43            int size = q.size();44            time++;45            for (int i = 0; i < size; i++) {46                int[] curr = q.poll();47                for (int[] dir : dirs) {48                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];49                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && fireTime[nr][nc] == Integer.MAX_VALUE) {50                        fireTime[nr][nc] = time;51                        q.offer(new int[]{nr, nc});52                    }53                }54            }55        }56    }57 58    private boolean canReach(int[][] grid, int[][] fireTime, int waitTime) {59        if (waitTime >= fireTime[0][0]) return false;60 61        java.util.Queue<int[]> q = new java.util.LinkedList<>();62        q.offer(new int[]{0, 0});63        boolean[][] visited = new boolean[m][n];64        visited[0][0] = true;65 66        int time = waitTime;67        while (!q.isEmpty()) {68            int size = q.size();69            time++;70            for (int i = 0; i < size; i++) {71                int[] curr = q.poll();72                for (int[] dir : dirs) {73                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];74                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {75                        if (nr == m - 1 && nc == n - 1) {76                            if (time <= fireTime[nr][nc]) return true;77                        }78                        if (time < fireTime[nr][nc]) {79                            visited[nr][nc] = true;80                            q.offer(new int[]{nr, nc});81                        }82                    }83                }84            }85        }86        return false;87    }88}

Complexity

Time

O(M*N * log(M*N)). The `fireTime` calculation is O(M*N). The binary search performs log(M*N) iterations, and in each iteration, it calls `canReach`, which takes O(M*N).

Space

O(M*N) for the `fireTime` grid, visited array, and BFS queues.

Trade-offs

Pros

Highly efficient and significantly faster than the linear scan approach.
Guaranteed to pass within the time limits for the given constraints.

Cons

The logic is slightly more complex due to the addition of the binary search framework.

Solutions

Solution

1class Solution {2private3  int[][] grid;4private5  boolean[][] fire;6private7  boolean[][] vis;8private9  final int[] dirs = {-1, 0, 1, 0, -1};10private11  int m;12private13  int n;14public15  int maximumMinutes(int[][] grid) {16    m = grid.length;17    n = grid[0].length;18    this.grid = grid;19    fire = new boolean[m][n];20    vis = new boolean[m][n];21    int l = -1, r = m * n;22    while (l < r) {23      int mid = (l + r + 1) >> 1;24      if (check(mid)) {25        l = mid;26      } else {27        r = mid - 1;28      }29    }30    return l == m * n ? 1000000000 : l;31  }32private33  boolean check(int t) {34    for (int i = 0; i < m; ++i) {35      Arrays.fill(fire[i], false);36      Arrays.fill(vis[i], false);37    }38    Deque<int[]> q1 = new ArrayDeque<>();39    for (int i = 0; i < m; ++i) {40      for (int j = 0; j < n; ++j) {41        if (grid[i][j] == 1) {42          q1.offer(new int[]{i, j});43          fire[i][j] = true;44        }45      }46    }47    for (; t > 0 && !q1.isEmpty(); --t) {48      q1 = spread(q1);49    }50    if (fire[0][0]) {51      return false;52    }53    Deque<int[]> q2 = new ArrayDeque<>();54    q2.offer(new int[]{0, 0});55    vis[0][0] = true;56    for (; !q2.isEmpty(); q1 = spread(q1)) {57      for (int d = q2.size(); d > 0; --d) {58        int[] p = q2.poll();59        if (fire[p[0]][p[1]]) {60          continue;61        }62        for (int k = 0; k < 4; ++k) {63          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];64          if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] && !vis[x][y] &&65              grid[x][y] == 0) {66            if (x == m - 1 && y == n - 1) {67              return true;68            }69            vis[x][y] = true;70            q2.offer(new int[]{x, y});71          }72        }73      }74    }75    return false;76  }77private78  Deque<int[]> spread(Deque<int[]> q) {79    Deque<int[]> nq = new ArrayDeque<>();80    while (!q.isEmpty()) {81      int[] p = q.poll();82      for (int k = 0; k < 4; ++k) {83        int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];84        if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] &&85            grid[x][y] == 0) {86          fire[x][y] = true;87          nq.offer(new int[]{x, y});88        }89      }90    }91    return nq;92  }93}

1class Solution {2public:3  int maximumMinutes(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    bool vis[m][n];6    bool fire[m][n];7    int dirs[5] = {-1, 0, 1, 0, -1};8    auto spread = [&](queue<pair<int, int>> &q) {9      queue<pair<int, int>> nq;10      while (q.size()) {11        auto [i, j] = q.front();12        q.pop();13        for (int k = 0; k < 4; ++k) {14          int x = i + dirs[k], y = j + dirs[k + 1];15          if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] &&16              grid[x][y] == 0) {17            fire[x][y] = true;18            nq.emplace(x, y);19          }20        }21      }22      return nq;23    };24    auto check = [&](int t) {25      memset(vis, false, sizeof(vis));26      memset(fire, false, sizeof(fire));27      queue<pair<int, int>> q1;28      for (int i = 0; i < m; ++i) {29        for (int j = 0; j < n; ++j) {30          if (grid[i][j] == 1) {31            q1.emplace(i, j);32            fire[i][j] = true;33          }34        }35      }36      for (; t && q1.size(); --t) {37        q1 = spread(q1);38      }39      if (fire[0][0]) {40        return false;41      }42      queue<pair<int, int>> q2;43      q2.emplace(0, 0);44      vis[0][0] = true;45      for (; q2.size(); q1 = spread(q1)) {46        for (int d = q2.size(); d; --d) {47          auto [i, j] = q2.front();48          q2.pop();49          if (fire[i][j]) {50            continue;51          }52          for (int k = 0; k < 4; ++k) {53            int x = i + dirs[k], y = j + dirs[k + 1];54            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&55                !fire[x][y] && grid[x][y] == 0) {56              if (x == m - 1 && y == n - 1) {57                return true;58              }59              vis[x][y] = true;60              q2.emplace(x, y);61            }62          }63        }64      }65      return false;66    };67    int l = -1, r = m * n;68    while (l < r) {69      int mid = (l + r + 1) >> 1;70      if (check(mid)) {71        l = mid;72      } else {73        r = mid - 1;74      }75    }76    return l == m * n ? 1e9 : l;77  }78};

1class Solution:2    def maximumMinutes(self, grid: List[List[int]]) -> int: def spread(q: Deque[int]) -> Deque[int]: nq = deque() while q: i, j = q . popleft() for a, b in pairwise(dirs): 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 nq . append((x, y)) return nq def check(t: int) -> bool: for i in range(m): for j in range(n): fire[i][j] = False q1 = deque() for i, row in enumerate(grid): for j, x in enumerate(row): if x == 1: fire[i][j] = True q1 . append((i, j)) while t and q1: q1 = spread(q1) t -= 1 if fire[0][0]: return False q2 = deque([(0, 0)]) vis = [[False] * n for _ in range(m)] vis[0][0] = True while q2: for _ in range(len(q2)): i, j = q2 . popleft() if fire[i][j]: continue for a, b in pairwise(dirs): x, y = i + a, j + b if (0 <= x < m and 0 <= y < n and not vis[x][y] and not fire[x][y] and grid[x][y] == 0): if x == m - 1 and y == n - 1: return True vis[x][y] = True q2 . append((x, y)) q1 = spread(q1) return False m, n = len(grid), len(grid[0]) l, r = - 1, m * n dirs = (- 1, 0, 1, 0, - 1) fire = [[False] * n for _ in range(m)] while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return int(1e9) if l == m * n else l

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem