LeetCode #73: Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/

One approach to solving this problem is to use the first row and column of the matrix to keep track of the rows and columns that need to be set to 0. We can first iterate through the first row and column of the matrix and check if they contain any zeros. If they do, we set two flags to indicate that the first row and column need to be set to 0.

Next, we iterate through the rest of the matrix and use the first row and column to keep track of the rows and columns that need to be set to 0. If an element in the matrix is 0, we set the corresponding element in the first row and column to 0.

Finally, we iterate through the first row and column and set the corresponding rows and columns in the matrix to 0 if their corresponding element in the first row or column is 0.

Here are the steps in detail:

1. Initialize two flags to indicate if the first row and column of the matrix need to be set to 0.
2. Iterate through the first row and column of the matrix and set the flags if they contain a 0.
3. Iterate through the rest of the matrix and use the first row and column to keep track of the rows and columns that need to be set to 0. If an element in the matrix is 0, set the corresponding element in the first row and column to 0.
4. Iterate through the first row and column of the matrix and set the corresponding rows and columns in the matrix to 0 if their corresponding element in the first row or column is 0.

Let’s take a look at the implementation of this approach:

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows = len(matrix)
        cols = len(matrix[0])

        first_row_zero = False
        first_col_zero = False

        # Check if first row contains zero
        for col in range(cols):
            if matrix[0][col] == 0:
                first_row_zero = True
                break

        # Check if first column contains zero
        for row in range(rows):
            if matrix[row][0] == 0:
                first_col_zero = True
                break

        # Use first row and column as markers for rows and columns to be set to zero
        for row in range(1, rows):
            for col in range(1, cols):
                if matrix[row][col] == 0:
                    matrix[0][col] = 0
                    matrix[row][0] = 0

        # Set corresponding rows and columns to zero
        for row in range(1, rows):
            for col in range(1, cols):
                if matrix[0][col] == 0 or matrix[row][0] == 0:
                    matrix[row][col] = 0

        # Set first row and column to zero if necessary
        if first_row_zero:
            for col in range(cols):
                matrix[0][col] = 0

        if first_col_zero:
            for row in range(rows):
                matrix[row][0] = 0

Time and Space Complexity

The time complexity of the solution is O(m*n), where m is the number of rows and n is the number of columns in the matrix. This is because we traverse the entire matrix twice – first to identify the rows and columns to be set to zero, and second to set them to zero.

The space complexity of the solution is O(m + n), where m is the number of rows and n is the number of columns in the matrix. This is because we use two sets to store the rows and columns to be set to zero, each of which can have a maximum size of m or n, respectively.