Set Matrix Zeroes

Problem Description

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Brute Force Solution

A brute force approach involves creating a copy of the matrix and then iterating through the original matrix. If we encounter a 0 in the original matrix, we set the corresponding row and column to 0's in the copied matrix. Finally, we overwrite the original matrix with the modified copied matrix.

Code

def set_matrix_zeroes_brute_force(matrix):
    m = len(matrix)
    n = len(matrix[0])
    
    # Create a copy of the matrix
    copied_matrix = [row[:] for row in matrix]
    
    # Iterate through original matrix
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                # Set row and column to 0 in the copied matrix
                for k in range(n):
                    copied_matrix[i][k] = 0
                for k in range(m):
                    copied_matrix[k][j] = 0
                    
    # Overwrite the original matrix
    for i in range(m):
        for j in range(n):
            matrix[i][j] = copied_matrix[i][j]

Time Complexity

O(m * n * (m + n)), where m is the number of rows and n is the number of columns.

Space Complexity

O(m * n) because we create a copy of the original matrix.

Optimal Solution

Instead of using O(m*n) space, we can use O(1) space. The idea is to use the first row and first column of the matrix as markers to indicate whether a row or column should be set to zero. Here's how it works:

1. Scan the first row and first column: Check if any element in the first row or first column is zero. If so, set row_has_zero or col_has_zero flags to true, respectively.
2. Iterate through the rest of the matrix: For each element matrix[i][j] (where i > 0 and j > 0), if it's zero, set matrix[i][0] and matrix[0][j] to zero. This marks that the i-th row and j-th column should be zeroed.
3. Zero out rows and columns: Iterate through the matrix again, starting from the second row and second column. If matrix[i][0] or matrix[0][j] is zero, set matrix[i][j] to zero.
4. Zero out the first row and first column: Finally, if row_has_zero is true, zero out the entire first row. If col_has_zero is true, zero out the entire first column.

Code

def set_matrix_zeroes_optimal(matrix):
    m = len(matrix)
    n = len(matrix[0])
    
    row_has_zero = False
    col_has_zero = False
    
    # Check if the first row contains a zero
    for j in range(n):
        if matrix[0][j] == 0:
            row_has_zero = True
            break
            
    # Check if the first column contains a zero
    for i in range(m):
        if matrix[i][0] == 0:
            col_has_zero = True
            break
            
    # Use the first row and first column as markers
    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
                
    # Zero out the rows and columns based on markers
    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
                
    # Zero out the first row if necessary
    if row_has_zero:
        for j in range(n):
            matrix[0][j] = 0
            
    # Zero out the first column if necessary
    if col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

Time Complexity

O(m * n), where m is the number of rows and n is the number of columns. We iterate through the matrix a few times.

Space Complexity

O(1), constant space, as we are modifying the matrix in-place.

Edge Cases

• Empty Matrix: If the input matrix is empty (either 0 rows or 0 columns), the algorithm should handle it gracefully, which it does without any special checks, because the loops won't execute.
• Matrix with Single Row or Column: The algorithm works correctly even if the matrix has only one row or one column.
• All Zeros Matrix: If the entire matrix contains only zeros, the algorithm will correctly set all elements to zero.
• No Zeros Matrix: If the matrix contains no zeros, the algorithm will not modify the matrix, as expected.