Set Matrix Zeroes

Understanding the Problem

The problem requires us to modify a given m x n matrix in-place. If any element in the matrix is 0, we need to set its entire row and column to 0s. The challenge lies in doing this efficiently, ideally with constant space complexity.

Brute Force Solution

A straightforward, but inefficient, approach involves using an auxiliary matrix of the same size to keep track of the cells that need to be zeroed out. We iterate through the original matrix. If we encounter a 0, we mark the corresponding row and column in the auxiliary matrix. Finally, we iterate through the auxiliary matrix and update the original matrix based on the marked rows and columns.

Code (Python)

def set_matrix_zeroes_brute_force(matrix):
    m = len(matrix)
    n = len(matrix[0])
    
    # Create an auxiliary matrix to mark rows and columns to be zeroed
    auxiliary_matrix = [[0] * n for _ in range(m)]
    
    # Iterate through the original matrix
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                # Mark the row and column in the auxiliary matrix
                for k in range(n):
                    auxiliary_matrix[i][k] = 1
                for k in range(m):
                    auxiliary_matrix[k][j] = 1
    
    # Update the original matrix based on the auxiliary matrix
    for i in range(m):
        for j in range(n):
            if auxiliary_matrix[i][j] == 1:
                matrix[i][j] = 0

    return matrix

Time and Space Complexity

• Time Complexity: O(m * n * (m + n)) in the worst case, where m is the number of rows and n is the number of columns. This is because for each zero element, we iterate through its entire row and column to mark the auxiliary matrix.
• Space Complexity: O(m * n), due to the auxiliary matrix used to store the marked rows and columns.

Optimal Solution: In-Place Modification

We can optimize the space complexity to O(1) by using the first row and first column of the matrix itself to store the information about which rows and columns need to be zeroed out. Here's how it works:

1. Use Flags: We use two flags, first_row_has_zero and first_col_has_zero, to check if the first row or first column initially contains any zeros.
2. Mark Rows and Columns: Iterate through the matrix (excluding the first row and first column). If matrix[i][j] is 0, set matrix[i][0] and matrix[0][j] to 0.
3. Zero Out Based on First Row and Column: Iterate through the matrix (excluding the first row and first column) again. If matrix[i][0] or matrix[0][j] is 0, set matrix[i][j] to 0.
4. Zero Out First Row and Column: Finally, based on the first_row_has_zero and first_col_has_zero flags, zero out the first row and first column if necessary.

Code (Python)

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

    # Check if the first row contains any zeros
    for j in range(n):
        if matrix[0][j] == 0:
            first_row_has_zero = True
            break

    # Check if the first column contains any zeros
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_has_zero = True
            break

    # Mark rows and columns in the first row and first column
    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 elements based on marks in the first row and first column
    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 first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0

    # Zero out the first column if necessary
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

    return matrix

Time and Space Complexity

• 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 constant number of times.
• Space Complexity: O(1), as we are using only a constant amount of extra space for the flags.

Edge Cases

• Empty Matrix: If the input matrix is empty (either m or n is 0), the algorithm should handle it gracefully (e.g., by returning without doing anything).
• Matrix with Single Row or Column: The algorithm should work correctly even if the matrix has only one row or one column.
• All Zeros: If the entire matrix contains zeros, the algorithm should correctly set all elements to zero.
• No Zeros: If the matrix contains no zeros, the algorithm should leave the matrix unchanged.