Set Matrix Zeroes medium

Problem Statement

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

Example 1:

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

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]]

Steps and Explanation:

The naive approach would be to iterate through the matrix, and whenever a 0 is found, iterate again to set the entire row and column to 0. However, this is inefficient (O(mnm) or O(mnn) time complexity). A more efficient approach uses the first row and column of the matrix to store information about whether a row or column needs to be zeroed.

1. First Pass: Iterate through the matrix. If you find a 0, set the corresponding first row element matrix[0][j] and first column element matrix[i][0] to 0. Note: We use matrix[0][j] and matrix[i][0] to mark, not to set the whole row and column to 0 yet. We also need to track if the first row or column itself contains a 0. We'll use separate variables for this.

2. Zeroing the Rows and Columns (excluding the first row and column): Iterate from row 1 to m-1 and column 1 to n-1. If matrix[i][0] or matrix[0][j] is 0, set matrix[i][j] to 0.

3. Zeroing the First Row and Column (if necessary): If matrix[0][0] was originally 0 (indicated by the first element being set to 0), we set the entire first row to 0. Similarly, if the first column should be set to 0 (indicated by any matrix[i][0] being 0), then set the entire first column to 0.

This approach cleverly uses the first row and column as a storage mechanism for information without needing extra space.

Code:

def setZeroes(matrix):
    """
    Sets rows and columns to zero if any element in the row or column is zero.

    Args:
        matrix: A list of lists representing the matrix.
    """
    rows = len(matrix)
    cols = len(matrix[0])
    first_row_has_zero = False
    first_col_has_zero = False

    # Check for zeros in the first row and column
    for i in range(rows):
        if matrix[i][0] == 0:
            first_col_has_zero = True
            break

    for j in range(cols):
        if matrix[0][j] == 0:
            first_row_has_zero = True
            break


    # Mark rows and cols that need to be zeroed
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # Set rows and cols to zero based on markings
    for i in range(1, rows):
        if matrix[i][0] == 0:
            for j in range(cols):
                matrix[i][j] = 0

    for j in range(1, cols):
        if matrix[0][j] == 0:
            for i in range(rows):
                matrix[i][j] = 0

    # Set first row and column to zero if needed
    if first_row_has_zero:
        for j in range(cols):
            matrix[0][j] = 0

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

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). We are doing the operation in place, using only a constant amount of extra space.