How do you handle the first row and column when setting zeros?

To handle the first row and column, you can use an extra variable to track if they need to be zeroed, and then modify them at the end after all other updates are made.

What are the space requirements for solving this problem?

The space complexity depends on your approach. Using hash sets to track rows and columns takes O(m + n) space, while the in-place method only requires O(1) extra space.

Can this problem be solved with constant space?

Yes, by modifying the matrix in place using the first row and first column to mark zero positions, you can solve the problem in constant space, O(1).

What if the matrix is sparse with many zeros?

The sparse nature of the matrix may not change the approach but may improve the performance of the hash set method due to fewer zero positions to track.

Is it necessary to use extra space for solving this problem?

No, you can solve this problem without extra space by using in-place modifications, though using additional memory with hash sets can simplify the approach.

#73

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。示例 1：输入： matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出： [[1,0,1],[0,0,0],[1,0,1]] 示例 2：输入： matrix …

数组哈希表矩阵

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

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

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2³¹ <= matrix[i][j] <= 2³¹ - 1

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

lightbulb

解题思路

Solution 1: Array Marking

Let the number of rows and columns of the matrix be $m$ and $n$ , respectively. We use an array $\textit{rows}$ of length $m$ and an array $\textit{cols}$ of length $n$ to record which rows and columns need to be set to zero.

First, we traverse the matrix. When we find a zero element in the matrix, we set the corresponding row and column markers to $\text{true}$ . That is, if $\textit{matrix}[i][j] = 0$ , then $\textit{rows}[i] = \textit{cols}[j] = \text{true}$ .

Finally, we traverse the matrix again and use the markers in $\textit{rows}$ and $\textit{cols}$ to update the elements in the matrix. When we find that $\textit{rows}[i]$ or $\textit{cols}[j]$ is $\text{true}$ , we set $\textit{matrix}[i][j]$ to zero.

The time complexity is $O(m \times n)$ , and the space complexity is $O(m + n)$ . Here, $m$ and $n$ are the number of rows and columns of the matrix, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        row = [False] * m
        col = [False] * n
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to modify a matrix in place without using additional space?
question_mark
Can you explain how you would handle edge cases such as when the first row or column has zeros?
question_mark
Will you optimize for space by using in-place modifications instead of extra memory?

warning

常见陷阱

外企场景

error
Overwriting the first row or column while marking zeroed rows and columns can lead to incorrect results if not handled properly.
error
Failing to correctly identify and handle edge cases, such as when the first row or column contains zeros.
error
Using too much extra space when a more efficient in-place solution is possible.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you were not allowed to use the first row and column to track the zero positions?
arrow_right_alt
How would you solve this problem if the matrix could contain negative numbers?
arrow_right_alt
Can you optimize this solution further to handle very large matrices, possibly with sparse zeros?

help

常见问题

外企场景

继续练习

#37 解数独 #36 有效的数独 #840 矩阵中的幻方