#73

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Set Matrix Zeroes

Modify the matrix in place by setting rows and columns to zero when an element is zero.

Problem Statement

You are given an m x n integer matrix. If any element of the matrix is zero, set its entire row and column to zero. The modification should be done in place, meaning no additional matrix is allowed.

For example, given the matrix [[1,1,1],[1,0,1],[1,1,1]], the output should be [[1,0,1],[0,0,0],[1,0,1]]. Your task is to solve this problem efficiently, focusing on handling zeros without using additional space beyond what is necessary.

Examples

Example 1

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[1,0,1],[0,0,0],[1,0,1]]

Example details omitted.

Example 2

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Example details omitted.

Constraints

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

Solution Approach

Using Hash Set (Extra Space)

First, iterate through the matrix to record the rows and columns that contain zeros using two sets. Then, iterate through the matrix again and set the rows and columns that have been recorded to zero. This approach uses extra space but simplifies tracking the rows and columns that need to be updated.

In-Place Modification (Constant Space)

A more space-efficient approach involves modifying the matrix in place. You can use the first row and first column to mark rows and columns that should be zeroed. After scanning the matrix, update the elements in the first row and first column based on the markings, and finally process the rest of the matrix. This eliminates the need for extra space.

Optimizing for Edge Cases

Special care must be taken when the first row or the first column contains zeros. To handle this, you can use a separate variable to track if the first row and first column themselves need to be zeroed. This ensures that the modifications do not overwrite critical data during the in-place marking process.

Complexity Analysis

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

The time complexity is O(m * n) as we need to iterate over the entire matrix twice. The space complexity is O(1) for the in-place modification approach, while the hash set method uses O(m + n) space to store the row and column indices.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Array Mark

We use arrays `rows` and `cols` to mark the rows and columns to be cleared.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Solution 2: Mark in Place

In the first method, we use an additional array to mark the rows and columns to be cleared. In fact, we can also use the first row and first column of the matrix to mark them, without creating an additional array.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#37 sudoku solver #36 valid sudoku #840 magic squares in grid