Set Matrix Zeroes

mediumFREEMath & GeometryBlind 75

Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Only zeros present in the original matrix trigger zeroing; zeros you write along the way do not. The function modifies matrix in place and returns nothing; the tests then print its rows, space-separated.

Example

Input

1,1,1
1,0,1
1,1,1

Output

1 0 1
0 0 0
1 0 1

Reasoning

Input: matrix is a $3 \times 3$ grid of integers, all 1s except a single 0 at row 1, column 1 (counting from 0).
Which lines get wiped: each original zero at position $(r, c)$ condemns all of row $r$ and all of column $c$ . Here the set of zero rows is $R = \{1\}$ and of zero columns $C = \{1\}$ .
Rule per cell: entry $(i, j)$ becomes 0 if $i \in R$ or $j \in C$ , otherwise it keeps its value. Row 1 becomes 0 0 0; column 1 zeroes the middle entry of rows 0 and 2; the four corners keep their 1s.
Output: the same grid, changed in place, printed row by row as 1 0 1, 0 0 0, 1 0 1.
Notice that $R$ and $C$ come only from zeros present before any change. The new zeros in row 1 must not spread further, or the whole grid would collapse to 0. A grid with no zeros comes back untouched.

Constraints

1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem "Set Matrix Zeroes" involves modifying a given matrix in-place, which means we need to update the original matrix without creating a new one. This requires understanding of matrix operations and how to traverse a matrix efficiently. In a matrix, each element is identified by its row and column index. To set an entire row or column to zero, we need to iterate over the corresponding indices and update the elements accordingly.

The problem also involves in-place modification, which is a common technique used in array and matrix problems. In-place modification means we are not allowed to create a new matrix or array to store the result; instead, we need to update the original data structure directly. This approach is useful when dealing with large datasets, as it helps reduce memory usage and improve performance. To achieve in-place modification, we need to use iterative techniques, such as loops, to traverse the matrix and update the elements.

In addition to matrix operations and in-place modification, this problem requires understanding of conditional statements and looping constructs. We need to check each element of the matrix and update the corresponding row and column if the element is zero. This involves using conditional statements, such as if statements, to check the value of each element and looping constructs, such as for loops, to iterate over the matrix.

Algorithm/Approach

The general approach to solve this type of problem involves using a combination of iterative techniques and conditional statements. We need to iterate over the matrix, check each element, and update the corresponding row and column if the element is zero. This can be achieved using nested loops, where the outer loop iterates over the rows and the inner loop iterates over the columns. We also need to use flags or markers to keep track of the rows and columns that need to be updated.

Step-by-Step Strategy

To implement the solution, we can follow these steps:

Initialize variables to keep track of the rows and columns that need to be updated.
Iterate over the matrix to identify the elements that are zero and update the corresponding row and column indices.
Use the row and column indices to update the matrix in-place.
Handle edge cases, such as an empty matrix or a matrix with a single row or column.

Common Pitfalls

When implementing the solution, we need to watch out for the following common pitfalls:

Forgetting to handle edge cases, such as an empty matrix or a matrix with a single row or column.
Using unnecessary extra space, which can lead to inefficient solutions.
Failing to update the matrix in-place, which can result in incorrect results.

Time & Space Complexity

The expected time complexity for this problem is $O(m \cdot n)$ , where $m$ is the number of rows and $n$ is the number of columns in the matrix. This is because we need to iterate over the entire matrix to identify the elements that are zero and update the corresponding rows and columns. The expected space complexity is $O(1)$ , as we need to update the matrix in-place without using any extra space that scales with the input size. However, we may need to use a small amount of extra space to store the row and column indices that need to be updated.

solution.py

Python 3.13

Test results