How do I solve the '01 Matrix' problem?

You can solve it by using a state transition dynamic programming approach with BFS, ensuring that each cell's distance to the nearest zero is calculated efficiently.

What is the time complexity of the '01 Matrix' problem?

The time complexity is O(m*n), as every cell in the matrix is processed once during the BFS traversal.

Can BFS be used for '01 Matrix'?

Yes, BFS is ideal for this problem as it explores all directions from zero and guarantees the shortest path to the nearest zero.

What are the common pitfalls in the '01 Matrix' problem?

Misunderstanding the problem as a greedy or DFS problem, not accounting for large input sizes, and incorrectly handling edge cases are common pitfalls.

What is the primary pattern for solving the '01 Matrix' problem?

The primary pattern for solving this problem is state transition dynamic programming, combined with BFS to propagate the minimal distances efficiently.

#542

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。示例 1：输入： mat = [[0,0,0],[0,1,0],[0,0,0]] 输出： [[0,0,0],[0,1,0],[0,…

数组动态规划广度优先搜索矩阵

题目描述

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m * n <= 10⁴
mat[i][j] is either 0 or 1.
mat 中至少有一个 0

lightbulb

解题思路

方法一：BFS

我们创建一个大小和 $\textit{mat}$ 一样的矩阵 $\textit{ans}$ ，并将所有的元素初始化为 $-1$ 。

然后我们遍历 $\textit{mat}$ ，将所有的 $0$ 元素的坐标 $(i, j)$ 加入队列 $\textit{q}$ ，并将 $\textit{ans}[i][j]$ 设为 $0$ 。

接下来，我们使用广度优先搜索，从队列中取出一个元素 $(i, j)$ ，并遍历其四个方向，如果该方向的元素 $(x, y)$ 满足 $0 \leq x < m$ , $0 \leq y < n$ 且 $\textit{ans}[x][y] = -1$ ，则将 $\textit{ans}[x][y]$ 设为 $\textit{ans}[i][j] + 1$ ，并将 $(x, y)$ 加入队列 $\textit{q}$ 。

最后返回 $\textit{ans}$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵 $\textit{mat}$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        ans = [[-1] * n for _ in range(m)]
        q = deque()
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                if x == 0:
                    ans[i][j] = 0
                    q.append((i, j))
        dirs = (-1, 0, 1, 0, -1)
        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 ans[x][y] == -1:
                    ans[x][y] = ans[i][j] + 1
                    q.append((x, y))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate is familiar with state transition dynamic programming techniques and can efficiently apply BFS for this type of problem.
question_mark
Candidate demonstrates an understanding of matrix-based problems and can optimize for large input sizes.
question_mark
Candidate can explain the trade-offs between time and space complexity in relation to solving matrix problems like '01 Matrix'.

warning

常见陷阱

外企场景

error
Misunderstanding the problem by treating it as a simple DFS or greedy problem instead of applying dynamic programming and BFS.
error
Not accounting for large input sizes, which could lead to inefficient solutions or memory overflows.
error
Incorrectly handling edge cases, such as matrices where zeros are scattered in non-trivial patterns.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solving the problem in a 3D matrix or with different distances (e.g., diagonal moves).
arrow_right_alt
Handling non-square matrices or matrices with more complex patterns of zeros.
arrow_right_alt
Optimizing for cases with only one zero in a massive matrix.

help

常见问题

外企场景

继续练习

#329 矩阵中的最长递增路径 #773 滑动谜题 #1162 地图分析