73.set-matrix-zeros.md

73. Set Matrix Zeroes

O(mn) Space Complexity

fun setZeroes(matrix: Array<IntArray>): Unit {
    val setZeroPositions = hashSetOf<Pair<Int, Int>>()
    val m = matrix.size
    val n = matrix[0].size
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (matrix[i][j] == 0) setZeroPositions.add(i to j)
        }
    }

    for (position in setZeroPositions) {
        setZero(matrix, position.first, position.second)
    }
}

private fun setZero(matrix: Array<IntArray>, row: Int, col: Int) {
    for (i in 0 until matrix.size) {
        matrix[i][col] = 0
    }
    for (j in 0 until matrix[0].size) {
        matrix[row][j] = 0
    }
}

O(m + n) Space Complexity

fun setZeroes(matrix: Array<IntArray>): Unit {
    val m = matrix.size
    val n = matrix[0].size
    val zeroRows = BooleanArray(m)
    val zeroCols = BooleanArray(n)
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (matrix[i][j] == 0) {
                zeroRows[i] = true
                zeroCols[j] = true
            }
        }
    }

    for (i in 0 until m) {
        for (j in 0 until n) {
            if (zeroRows[i] || zeroCols[j]) {
                matrix[i][j] = 0
            }
        }
    }
}

O(1) Space Complexity

Idea!! We can use the first row and column to keep track of whether that row/column has to set zero, but before that, we have to know whether the first row/column itself contains zero first.

// Original
5, 5, 5
0, 5, 0
5, 5, 5

// If we don't check the first row/column first, we will get the wrong result
5, 5, 0
0, 5, 5
5, 5, 5

// It leads to the wrong result
5, 5, 0
0, 0, 0
5, 5, 0

// But the correct result is
0, 5, 0
0, 0, 0
0, 5, 0

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

    row0 = False
    col0 = False
    for i in range(0, m):
        for j in range(0, n):
            if matrix[i][j] == 0:
                if i == 0: row0 = True
                if j == 0: col0 = True
                if i > 0 and j > 0: 
                    matrix[0][j] = 0
                    matrix[i][0] = 0
    
    for i in range(1, m):
        for j in range(1, n):
            if matrix[0][j] == 0 or matrix[i][0] == 0:
                matrix[i][j] = 0
    
    if row0:
        for j in range(0, n):
            matrix[0][j] = 0
    if col0:
        for i in range(0, m):
            matrix[i][0] = 0

fun setZeroes(matrix: Array<IntArray>): Unit {
    val m = matrix.size
    val n = matrix[0].size
    var firstRowContainsZero = false
    var firstColContainsZero = false
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (matrix[i][j] == 0) {
                if (i == 0) firstRowContainsZero = true
                if (j == 0) firstColContainsZero = true
                if (i != 0 && j != 0) {
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                }
            }
        }
    }

    // We have to set rows/columns other than the first one first.
    for (i in 1 until m) {
        for (j in 1 until n) {
            if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0
        }
    }

    // Then set zeros for the first row/columns
    if (firstRowContainsZero) {
        for (j in 0 until n) matrix[0][j] = 0
    }
    if (firstColContainsZero) {
        for (i in 0 until m) matrix[i][0] = 0
    }
}

• Time Complexity: O(mn).
• Space Complexity: O(1).