Escape the Spreading Fire

Escape the Spreading Fire

What is this problem about?

The Escape the Spreading Fire interview question is a high-stakes survival challenge on a grid. You are in a field with grass, walls, a safe house, and several initial fire locations. Every minute, the fire spreads to adjacent grass cells. You can also move one cell per minute. You need to find the maximum amount of time you can "wait" at the start and still be able to reach the safe house without being caught by the fire. If you can't reach it even without waiting, return -1.

Why is this asked in interviews?

Companies like Uber and Google use the Escape the Spreading Fire coding problem to test a candidate's ability to combine multiple algorithmic techniques. It requires modeling a dynamic environment (the spreading fire) and optimizing a "waiting time" variable. It evaluates your proficiency with Breadth-First Search (BFS) and Binary Search.

Algorithmic pattern used

This problem uses a Multi-source BFS combined with Binary Search on the Answer.

1. Fire BFS: First, perform a multi-source BFS to calculate the earliest time the fire reaches every cell in the grid.
2. Binary Search: You want to find the maximum wait_time. The range is [0, grid_area].
3. Validation BFS: For a given wait_time, perform another BFS to see if you can reach the safe house. A cell (r, c) is only traversable at time T if T < fire_arrival_time[r][c]. (Special rules usually apply to the safe house arrival).

Example explanation

Imagine a 5x5 grid. Fire starts at (0, 0). You are at (4, 4). Safe house is at (0, 4). If you start immediately, you reach the house in 4 minutes. The fire takes 4 minutes to reach (0, 4). Depending on the rules, you might be safe. If you wait 1 minute, the fire has already spread to (0, 1) and (1, 0). Now you must reach the house faster than the fire. The binary search helps you find the exact threshold where you can no longer outrun the flames.

Common mistakes candidates make

• Safe House Edge Case: Forgetting that you and the fire can reach the safe house at the same time if you are coming from a safe direction (check the specific problem wording).
• Redundant Fire Calculation: Re-calculating fire spread for every step of the binary search instead of pre-calculating it once.
• BFS State: Not tracking visited cells correctly in the validation phase.

Interview preparation tip

Master the "Multi-source BFS" pattern. It is the standard way to calculate "distance to the nearest X" for all points in a grid simultaneously.