Escape the Spreading Fire

Hard
927.

Escape the Spreading Fire

Escape the Spreading Fire is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

A grid holds 0 for grass, 1 for fire and 2 for a wall. You start at the top-left cell and want to reach the safehouse at the bottom-right.

Each minute you may move one cell up, down, left or right onto grass, and then the fire spreads to every grass cell adjacent to a burning one. Walls block both of you. You may first wait in place for some minutes before setting off — but not while your cell is on fire.

Return the maximum number of minutes you can wait and still reach the safehouse, or -1 if you cannot reach it even without waiting. If you can wait forever, return 10^9.

Reaching the safehouse at the very minute the fire arrives there still counts as escaping.

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

Example 2

Input
grid = [[0,0,0,0],[0,1,2,0],[0,2,2,0],[0,0,0,0]]
Output
-1
Explanation
The fire reaches every route before you do.

Example 3

Input
grid = [[0,0,0],[2,2,0],[1,2,0]]
Output
1000000000
Explanation
Walls pen the fire in, so it never spreads.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 300
  • 4 <= m * n <= 2 * 10^4
  • grid[i][j] is 0, 1 or 2
  • grid[0][0] == grid[m-1][n-1] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maximumMinutes = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Escape the Spreading Fire — Solution in Python, Java & C++

Escape the Spreading Fire solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Escape the Spreading Fire is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

Problem statement

A grid holds 0 for grass, 1 for fire and 2 for a wall. You start at the top-left cell and want to reach the safehouse at the bottom-right.

Each minute you may move one cell up, down, left or right onto grass, and then the fire spreads to every grass cell adjacent to a burning one. Walls block both of you. You may first wait in place for some minutes before setting off — but not while your cell is on fire.

Return the maximum number of minutes you can wait and still reach the safehouse, or -1 if you cannot reach it even without waiting. If you can wait forever, return 10^9.

Reaching the safehouse at the very minute the fire arrives there still counts as escaping.

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

Example 2

Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,2,0],[0,0,0,0]]
Output: -1
Explanation: The fire reaches every route before you do.

Example 3

Input: grid = [[0,0,0],[2,2,0],[1,2,0]]
Output: 1000000000
Explanation: Walls pen the fire in, so it never spreads.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 300
  • 4 <= m * n <= 2 * 10^4
  • grid[i][j] is 0, 1 or 2
  • grid[0][0] == grid[m-1][n-1] == 0

Hints for Escape the Spreading Fire

  1. Hint 1

    First compute, with a multi-source BFS, the minute the fire reaches each cell — infinity for cells it never reaches.

  2. Hint 2

    Waiting longer is never easier: if you can escape after waiting t, you can escape after waiting t - 1. That monotonicity invites a binary search.

  3. Hint 3

    For a fixed wait, a BFS works: you may step onto a cell only strictly before the fire gets there — except the safehouse, where arriving together is enough.

How to solve Escape the Spreading Fire

Precompute the fire's arrival time everywhere, then binary search the wait. For a candidate wait, one BFS decides whether a safe route exists.

Approach

  1. Multi-source BFS from the fire cells through grass only, giving fire[cell].
  2. canEscape(t): BFS from the start with clock beginning at t; step onto a cell only if arrival < fire[cell].
  3. At the safehouse, accept arrival <= fire[cell] instead.
  4. Binary search the largest t in [0, m·n]. If even m·n works, the fire can never catch you — return 10^9; if 0 fails, return -1.

Why it works

Monotonicity is what makes the binary search valid: the route that works after waiting t also works after waiting less, since every arrival time only shrinks while the fire's schedule is fixed. And m·n is a safe upper bound — a route has at most m·n cells, so if waiting that long still works, no reachable cell is ever on fire ahead of you.

Complexity

  • Time — O(m · n · log(m · n))
  • Space — O(m · n)

Pitfalls

  • The safehouse's <= rule is a genuine special case; using < there loses cases.
  • Cells the fire never reaches need an infinite arrival time, not zero.
  • You cannot wait on a burning start cell, so canEscape(t) must reject t >= fire[start].

Reference solution

Python

from typing import List
from collections import deque

def maximumMinutes(grid: List[List[int]]) -> int:
    BIG = 1000000000
    m, n = len(grid), len(grid[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    fire = [[BIG] * n for _ in range(m)]
    q = deque()
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                fire[i][j] = 0
                q.append((i, j))
    while q:
        r, c = q.popleft()
        for di, dj in dirs:
            nr, nc = r + di, c + dj
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 2 and fire[nr][nc] == BIG:
                fire[nr][nc] = fire[r][c] + 1
                q.append((nr, nc))

    def can_escape(wait: int) -> bool:
        if fire[0][0] <= wait:
            return False
        seen = [[False] * n for _ in range(m)]
        seen[0][0] = True
        bq = deque([(0, 0, wait)])
        while bq:
            r, c, t = bq.popleft()
            for di, dj in dirs:
                nr, nc = r + di, c + dj
                if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] == 2 or seen[nr][nc]:
                    continue
                at = t + 1
                if nr == m - 1 and nc == n - 1:
                    if fire[nr][nc] >= at:
                        return True
                    continue
                if fire[nr][nc] <= at:
                    continue
                seen[nr][nc] = True
                bq.append((nr, nc, at))
        return False

    if not can_escape(0):
        return -1
    hi = m * n
    if can_escape(hi):
        return BIG
    lo = 0
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if can_escape(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Java

public static int maximumMinutes(int[][] grid) {
    final int BIG = 1000000000;
    int m = grid.length, n = grid[0].length;
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int[] fire = new int[m * n];
    Arrays.fill(fire, BIG);
    int[] q = new int[m * n];
    int head = 0, tail = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) { fire[i * n + j] = 0; q[tail++] = i * n + j; }
        }
    }
    while (head < tail) {
        int cur = q[head++];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int key = nr * n + nc;
            if (grid[nr][nc] == 2 || fire[key] < BIG) continue;
            fire[key] = fire[cur] + 1;
            q[tail++] = key;
        }
    }
    if (!escapeOk(grid, fire, 0)) return -1;
    int hi = m * n;
    if (escapeOk(grid, fire, hi)) return BIG;
    int lo = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (escapeOk(grid, fire, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

private static boolean escapeOk(int[][] grid, int[] fire, int wait) {
    int m = grid.length, n = grid[0].length;
    if (fire[0] <= wait) return false;
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    boolean[] seen = new boolean[m * n];
    int[] time = new int[m * n];
    int[] q = new int[m * n];
    int head = 0, tail = 0;
    seen[0] = true;
    time[0] = wait;
    q[tail++] = 0;
    while (head < tail) {
        int cur = q[head++];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int key = nr * n + nc;
            if (grid[nr][nc] == 2 || seen[key]) continue;
            int at = time[cur] + 1;
            if (nr == m - 1 && nc == n - 1) {
                if (fire[key] >= at) return true;
                continue;
            }
            if (fire[key] <= at) continue;
            seen[key] = true;
            time[key] = at;
            q[tail++] = key;
        }
    }
    return false;
}

C++

static bool escapeOk(vector<vector<int>>& grid, vector<int>& fire, int wait) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    if (fire[0] <= wait) return false;
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    vector<char> seen(m * n, 0);
    vector<int> time(m * n, 0), q;
    seen[0] = 1;
    time[0] = wait;
    q.push_back(0);
    for (size_t head = 0; head < q.size(); head++) {
        int cur = q[head];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int key = nr * n + nc;
            if (grid[nr][nc] == 2 || seen[key]) continue;
            int at = time[cur] + 1;
            if (nr == m - 1 && nc == n - 1) {
                if (fire[key] >= at) return true;
                continue;
            }
            if (fire[key] <= at) continue;
            seen[key] = 1;
            time[key] = at;
            q.push_back(key);
        }
    }
    return false;
}

int maximumMinutes(vector<vector<int>>& grid) {
    const int BIG = 1000000000;
    int m = (int) grid.size(), n = (int) grid[0].size();
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    vector<int> fire(m * n, BIG), q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) { fire[i * n + j] = 0; q.push_back(i * n + j); }
        }
    }
    for (size_t head = 0; head < q.size(); head++) {
        int cur = q[head];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int key = nr * n + nc;
            if (grid[nr][nc] == 2 || fire[key] < BIG) continue;
            fire[key] = fire[cur] + 1;
            q.push_back(key);
        }
    }
    if (!escapeOk(grid, fire, 0)) return -1;
    int hi = m * n;
    if (escapeOk(grid, fire, hi)) return BIG;
    int lo = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (escapeOk(grid, fire, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

JavaScript

var maximumMinutes = function(grid) {
    var BIG = 1000000000;
    var m = grid.length, n = grid[0].length, i, j, d;
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var fire = [];
    for (i = 0; i < m * n; i++) fire.push(BIG);
    var q = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] === 1) { fire[i * n + j] = 0; q.push(i * n + j); }
        }
    }
    var head = 0;
    while (head < q.length) {
        var cur = q[head++];
        var r = Math.floor(cur / n), c = cur % n;
        for (d = 0; d < 4; d++) {
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            var key = nr * n + nc;
            if (grid[nr][nc] === 2 || fire[key] < BIG) continue;
            fire[key] = fire[cur] + 1;
            q.push(key);
        }
    }
    var canEscape = function(wait) {
        if (fire[0] <= wait) return false;
        var seen = [], time = [];
        for (var t = 0; t < m * n; t++) { seen.push(false); time.push(0); }
        seen[0] = true;
        time[0] = wait;
        var bq = [0], h = 0;
        while (h < bq.length) {
            var cur2 = bq[h++];
            var r2 = Math.floor(cur2 / n), c2 = cur2 % n;
            for (var dd = 0; dd < 4; dd++) {
                var ar = r2 + dr[dd], ac = c2 + dc[dd];
                if (ar < 0 || ar >= m || ac < 0 || ac >= n) continue;
                var k = ar * n + ac;
                if (grid[ar][ac] === 2 || seen[k]) continue;
                var at = time[cur2] + 1;
                if (ar === m - 1 && ac === n - 1) {
                    if (fire[k] >= at) return true;
                    continue;
                }
                if (fire[k] <= at) continue;
                seen[k] = true;
                time[k] = at;
                bq.push(k);
            }
        }
        return false;
    };
    if (!canEscape(0)) return -1;
    var hi = m * n;
    if (canEscape(hi)) return BIG;
    var lo = 0;
    while (lo < hi) {
        var mid = lo + Math.floor((hi - lo + 1) / 2);
        if (canEscape(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search