Set Matrix Zeroes

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

Could you please write a function that takes a 2D array (matrix) of integers as input and modifies it according to the following rules:

1. If any element in the matrix is 0, all elements in its row and its column must be set to 0.
2. The modification must be done in-place.

Here are a few examples to illustrate the expected behavior:

• Example 1:

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

• Example 2:

  Input: [ [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 3:

  Input: [[1,2,3],[4,0,6],[7,8,9]] Output: [[1,0,3],[0,0,0],[7,0,9]]

Can you implement this in an efficient manner?

Set Matrix Zeroes

Let's dive into the 'Set Matrix Zeroes' problem. Given a matrix (a 2D array), if any element in the matrix is 0, we need to set its entire row and column to 0. We'll explore a couple of approaches.

1. Naive (Brute Force) Solution

The most straightforward approach is to iterate through the matrix. When we find a 0, we record the row and column indices. Then, in separate iterations, we'll set the corresponding rows and columns to 0.

Algorithm:

1. Scan the matrix, and if matrix[i][j] == 0, store i in a rows set and j in a cols set.
2. Iterate through the rows set, and for each row r, set all elements in matrix[r][:] to 0.
3. Iterate through the cols set, and for each column c, set all elements in matrix[:][c] to 0.

Code (Python):

python def set_matrix_zeroes_naive(matrix): rows = set() cols = set() m = len(matrix) n = len(matrix[0]) if m > 0 else 0

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            rows.add(i)
            cols.add(j)

for row in rows:
    for j in range(n):
        matrix[row][j] = 0

for col in cols:
    for i in range(m):
        matrix[i][col] = 0

return matrix

Big O Analysis:

• Time Complexity: O(mn + m + n). Scanning the matrix takes O(mn), and iterating through rows and cols takes O(m) and O(n) respectively.
• Space Complexity: O(m + n) due to the rows and cols sets storing row and column indices.

2. Optimal Solution (In-Place)

We can optimize the space complexity to O(1) by utilizing the first row and first column of the matrix to store the row and column information (instead of using separate sets).

Algorithm:

1. Check if the first row or first column contains any zeroes. We need to track this separately since we'll be using the first row/col for storage.
2. Iterate through the matrix (excluding the first row and column). If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
3. Iterate through the first row, and if matrix[0][j] == 0, set the entire column j to 0.
4. Iterate through the first column, and if matrix[i][0] == 0, set the entire row i to 0.
5. Finally, if the first row or column initially contained zeroes, set the entire row/column to zero.

Code (Python):

python def set_matrix_zeroes_optimal(matrix): m = len(matrix) n = len(matrix[0]) if m > 0 else 0 first_row_has_zero = False first_col_has_zero = False

# Check if first row has zero
for j in range(n):
    if matrix[0][j] == 0:
        first_row_has_zero = True
        break

# Check if first col has zero
for i in range(m):
    if matrix[i][0] == 0:
        first_col_has_zero = True
        break

# Mark rows and cols
for i in range(1, m):
    for j in range(1, n):
        if matrix[i][j] == 0:
            matrix[i][0] = 0
            matrix[0][j] = 0

# Use mark to set elements
for i in range(1, m):
    for j in range(1, n):
        if matrix[i][0] == 0 or matrix[0][j] == 0:
            matrix[i][j] = 0

# Set first row and col
if first_row_has_zero:
    for j in range(n):
        matrix[0][j] = 0

if first_col_has_zero:
    for i in range(m):
        matrix[i][0] = 0

return matrix

Big O Analysis:

• Time Complexity: O(mn). We iterate through the matrix a few times.
• Space Complexity: O(1). We are using constant extra space (in-place).

Edge Cases

• Empty Matrix: Handle the case where the matrix is empty or has zero rows/columns. The code gracefully handles empty matrices by returning them without modification.
• Single Row/Column Matrix: The algorithm works correctly for single row or column matrices.
• All Zero Matrix: The algorithm also handles the case where all elements in the matrix are zero.

In summary, the optimal solution provides a space-efficient way to solve the Set Matrix Zeroes problem.