How hard is LeetCode 2258. Escape the Spreading Fire?

LeetCode 2258. Escape the Spreading Fire is rated Hard on LeetCode.

What is the time complexity of LeetCode 2258. Escape the Spreading Fire?

The Python solution on this page runs in O(m \times n \times \log (m \times n)).

What is the space complexity of LeetCode 2258. Escape the Spreading Fire?

The Python solution on this page uses O(m \times n) auxiliary space.

What topics does LeetCode 2258. Escape the Spreading Fire cover?

LeetCode 2258. Escape the Spreading Fire is tagged Breadth-First Search, Array, Binary Search and Matrix on LeetCode.

Escape the Spreading Fire — LeetCode 2258 Python Solution

HardBreadth-First SearchArrayBinary SearchMatrix

Problem: #2258
Pattern: Matrix and Grid
Reading time: 11 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(m \times n \times \log (m \times n))
Space	O(m \times n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2258. Escape the Spreading Fire is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2258. Escape the Spreading Fire?: LeetCode 2258. Escape the Spreading Fire is rated Hard on LeetCode.
What is the time complexity of LeetCode 2258. Escape the Spreading Fire?: The Python solution on this page runs in O(m \times n \times \log (m \times n)).
What is the space complexity of LeetCode 2258. Escape the Spreading Fire?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 2258. Escape the Spreading Fire cover?: LeetCode 2258. Escape the Spreading Fire is tagged Breadth-First Search, Array, Binary Search and Matrix on LeetCode.