AlgoBreath

Set Matrix Zeroes

Problem Statement: Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. Do it in-place without using any extra space.

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

Solution: To solve this problem using constant extra space, we can use the first row and first column of the matrix itself to keep track of the rows and columns that need to be set to 0. Here's the step-by-step algorithm:

  1. Initialize two boolean variables, firstRow and firstCol, to false. These variables will indicate whether the first row and first column need to be set to 0 at the end.

  2. Iterate through the matrix starting from the second row and second column:

    • If an element is 0, set the corresponding element in the first row and first column to 0.

  3. Iterate through the matrix starting from the second row and second column again:

    • If the element in the first row or first column is 0, set the current element to 0.

  4. If firstRow is true, set all elements in the first row to 0. If firstCol is true, set all elements in the first column to 0.

  5. The matrix will now have the desired result.

Here's the code implementation in Python:

def setZeroes(matrix):
    m = len(matrix)
    n = len(matrix[0])
    firstRow = False
    firstCol = False

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

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

    # Use the first row and first column to mark the rows and columns to be set to zero
    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

    # Set the marked rows and columns to zero
    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 the first row to zero if necessary
    if firstRow:
        for j in range(n):
            matrix[0][j] = 0

    # Set the first column to zero if necessary
    if firstCol:
        for i in range(m):
            matrix[i][0] = 0

    return matrix

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix. Since we are using the first row and first column of the matrix itself to store the information, the space complexity is O(1), i.e., constant extra space.

The key idea is to use the first row and first column as markers to indicate which rows and columns need to be set to 0. We first check if the first row and first column themselves contain any zeros. Then, we iterate through the matrix starting from the second row and second column, and if an element is 0, we set the corresponding element in the first row and first column to 0. Finally, we iterate through the matrix again and set the elements to 0 based on the markers in the first row and first column.

PrevNext