#2258

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Escape the Spreading Fire

Maximize the time you can stay at your starting position before moving to safely reach the safehouse while avoiding fire.

array binary search breadth first search matrix

Problem Statement

You are in the top-left corner of a grid with a fire spreading from various cells. Your goal is to determine the maximum number of minutes you can stay in your position before moving while ensuring you can safely reach the safehouse at the bottom-right corner. Fire spreads every minute to adjacent cells, and you can only move to adjacent grass cells.

If you can always reach the safehouse regardless of how long you stay, return 109. If it’s impossible to ever reach the safehouse, return -1. The grid contains walls, grass, and fire, and you must account for the spreading fire while figuring out your escape path.

Examples

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

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

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

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

Solution Approach

Binary Search for Maximum Stay Time

Perform binary search on the possible number of minutes you can stay at the initial position, adjusting the range based on whether you can still reach the safehouse after that time. This optimizes the search for the solution without checking every individual minute.

Breadth-First Search (BFS) for Pathfinding

BFS is used to simulate the fire's spread and determine the time it reaches each cell. Once you know how long the fire will take to reach different cells, you can check if there’s a safe path to the safehouse for each candidate time.

Fire Spread Simulation

For each possible starting time from the binary search, simulate the fire’s spread and validate if the safehouse is reachable. This step ensures you can verify the feasibility of the candidate times.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity mainly depends on the binary search steps (O(log(min(m, n)))) and BFS (O(m * n)), leading to a combined complexity of O((m * n) * log(min(m, n))). The space complexity is O(m * n) due to the BFS and grid storage.

What Interviewers Usually Probe

Look for a candidate who can handle the combination of binary search and BFS effectively.
Assess if the candidate understands how fire spread impacts pathfinding and timing.
Evaluate the candidate's approach to handling large grids and efficient time management.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding how fire spreads and when it reaches each cell, leading to incorrect time estimations.
Failing to account for edge cases where the fire immediately blocks the path to the safehouse.
Not optimizing the solution with binary search, leading to unnecessary time complexity.

Follow-up variants

Consider grids with more complex fire spread patterns, including diagonal spreads or multiple fire sources.
Change the problem’s constraints to allow multiple safehouses and examine how that impacts the solution.
Alter the fire spread rules, such as allowing the fire to spread slower or faster, and analyze the effect on the algorithm.

FAQ

What is the role of binary search in this problem?

Binary search is used to find the maximum number of minutes you can stay at the initial position while still being able to safely reach the safehouse.

Why can't I use brute force to solve this problem?

Brute force would involve checking every possible time, which is inefficient for large grids. Binary search dramatically reduces the number of checks needed.

How does BFS help in this problem?

BFS helps simulate the fire's spread and check whether a path to the safehouse exists at a specific time, ensuring safety while moving.

What happens if the fire blocks the entire path?

If the fire blocks all paths, the function returns -1, indicating it’s impossible to reach the safehouse safely.

How does GhostInterview help with this problem?

GhostInterview helps you practice binary search in a grid and refine your approach to simulating fire spread and pathfinding.

terminal

Solution

Solution 1: Binary Search + BFS

We notice that if a stay time $t$ satisfies the condition, then all stay times less than $t$ also satisfy the condition. Therefore, we can consider using binary search to find the maximum stay time that satisfies the condition.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

class Solution:
    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

Continue Practicing

#1970 last day where you can still cross #2812 find the safest path in a grid #1631 path with minimum effort