Escape the Spreading Fire - Practice Coding Problems

Escape the Spreading Fire - Problem

Escape the Spreading Fire

You find yourself trapped in a burning field represented by a 2D grid, where you must escape from the top-left corner (0,0) to a safehouse at the bottom-right corner while avoiding the spreading flames!

🌱 0 = Grass (safe to walk on)
🔥 1 = Fire (spreads every minute)
🧱 2 = Wall (blocks both you and fire)

The challenge: What's the maximum time you can wait before starting your escape?

Game Rules:
• You can move to adjacent grass cells (up, down, left, right)
• After each of your moves, fire spreads to all adjacent non-wall cells
• You need to reach the safehouse before being caught by fire
• If you can reach safely regardless of wait time, return 10⁹
• If escape is impossible, return -1

Victory Condition: Even if fire reaches the safehouse right after you arrive, you still win! 🎯

Input & Output

example_1.py — Basic Escape

$ 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

💡 Note: You can wait 3 minutes at the starting position before moving. The fire will spread but you can still find a safe path to the bottom-right corner by going around the walls and avoiding the spreading flames.

example_2.py — Impossible Escape

$ Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]

› Output: -1

💡 Note: The fire will spread and block all possible paths to the destination. No matter when you start moving, you cannot reach the safehouse safely.

example_3.py — Unlimited Time

$ Input: grid = [[0,0,0],[2,2,0],[0,0,0]]

› Output: 1000000000

💡 Note: There is no fire in the grid (only walls and grass), so you can wait indefinitely and still reach the safehouse. The walls don't block your optimal path.

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

Asked in

The optimal solution uses binary search on the waiting time combined with BFS pathfinding. Key insight: if we can escape after waiting X minutes, we can also escape after waiting fewer minutes, creating a monotonic property perfect for binary search. Time complexity: O(m × n × log(m × n)).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search + BFS (Optimal)	O(m × n × log(m × n))	O(m × n)	Use binary search on waiting time combined with efficient fire simulation and BFS pathfinding
Brute Force Simulation	O(T × m × n)	O(m × n)	Test every possible waiting time by simulating fire spread and pathfinding

Binary Search + BFS (Optimal) — Algorithm Steps

Precompute fire spread times for all cells using multi-source BFS
Binary search on waiting time from 0 to reasonable upper bound
For each candidate time, simulate player movement with BFS
Check if player can reach destination before fire catches up
Narrow search range based on feasibility of current waiting time

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Fire Times

Use multi-source BFS to calculate when fire reaches each cell

Binary Search Setup

Set search range from 0 to m×n and find middle point

Test Waiting Time

For current candidate, simulate player movement with BFS

Narrow Search

Based on result, search upper or lower half

Find Maximum

Continue until we find the maximum feasible waiting time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_QUEUE 10000

typedef struct {
    int x, y, time;
} Position;

int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int m, n;
int** globalGrid;

int** getFireTimes() {
    int** fireTime = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        fireTime[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            fireTime[i][j] = -1;
        }
    }
    
    Position queue[MAX_QUEUE];
    int front = 0, rear = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (globalGrid[i][j] == 1) {
                fireTime[i][j] = 0;
                queue[rear++] = (Position){i, j, 0};
            }
        }
    }
    
    while (front < rear) {
        Position curr = queue[front++];
        
        for (int d = 0; d < 4; d++) {
            int nx = curr.x + directions[d][0];
            int ny = curr.y + directions[d][1];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                globalGrid[nx][ny] == 0 && fireTime[nx][ny] == -1) {
                fireTime[nx][ny] = curr.time + 1;
                queue[rear++] = (Position){nx, ny, curr.time + 1};
            }
        }
    }
    
    return fireTime;
}

bool canEscapeWithDelay(int delay) {
    int** fireTime = getFireTimes();
    
    if (fireTime[0][0] != -1 && fireTime[0][0] <= delay) {
        for (int i = 0; i < m; i++) free(fireTime[i]);
        free(fireTime);
        return false;
    }
    
    Position queue[MAX_QUEUE];
    bool visited[100][100] = {false};
    int front = 0, rear = 0;
    
    queue[rear++] = (Position){0, 0, delay};
    visited[0][0] = true;
    
    while (front < rear) {
        Position curr = queue[front++];
        
        for (int d = 0; d < 4; d++) {
            int nx = curr.x + directions[d][0];
            int ny = curr.y + directions[d][1];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                !visited[nx][ny] && globalGrid[nx][ny] != 2) {
                
                int arrivalTime = curr.time + 1;
                
                if (nx == m-1 && ny == n-1) {
                    if (fireTime[nx][ny] == -1 || fireTime[nx][ny] >= arrivalTime) {
                        for (int i = 0; i < m; i++) free(fireTime[i]);
                        free(fireTime);
                        return true;
                    }
                } else {
                    if (fireTime[nx][ny] == -1 || fireTime[nx][ny] > arrivalTime) {
                        visited[nx][ny] = true;
                        queue[rear++] = (Position){nx, ny, arrivalTime};
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < m; i++) free(fireTime[i]);
    free(fireTime);
    return false;
}

int maximumMinutes(int** grid, int gridSize, int* gridColSize) {
    globalGrid = grid;
    m = gridSize;
    n = gridColSize[0];
    
    if (!canEscapeWithDelay(0)) return -1;
    
    int left = 0, right = m * n;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (canEscapeWithDelay(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result == m * n ? 1000000000 : result;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × log(m × n))

Binary search has log(m×n) iterations, each doing O(m×n) BFS for fire and player simulation

⚡ Linearithmic

Space Complexity

O(m × n)

Grid storage, fire times array, and BFS queue space

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen