33. Set Matrix Zeroes

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

Examples:

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

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

Problem Breakdown:

  1. Use the first row and first column as markers. First, check if the first row or first column originally contain zeros.
    • m, n = len(matrix), len(matrix[0])
firstRowZero = any(matrix[0][j] == 0 for j in range(n))
firstColZero = any(matrix[i][0] == 0 for i in range(m))
  2. Scan the rest of the matrix. When a zero is found, mark its row and column by setting the corresponding first row and first column cell to 0.
    • 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
  3. Use the markers to zero out the appropriate cells in the inner matrix.
    • 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
  4. Finally, zero out the first row and first column if they originally contained zeros.
    • if firstRowZero:
    for j in range(n): matrix[0][j] = 0
if firstColZero:
    for i in range(m): matrix[i][0] = 0

Summary:

Use the first row and column as in-place markers. Record which rows/columns need zeroing by marking their first-row/first-column cells. Then apply the zeroing from the markers. Handle the first row and column separately since they serve as markers.

Time and Space Complexity:

Time Complexity: O(m * n) - we scan the matrix a constant number of times.

Space Complexity: O(1) - we use the matrix itself as storage for markers.

Python Solution:

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    firstRowZero = any(matrix[0][j] == 0 for j in range(n))
    firstColZero = any(matrix[i][0] == 0 for i in range(m))
    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
    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
    if firstRowZero:
        for j in range(n):
            matrix[0][j] = 0
    if firstColZero:
        for i in range(m):
            matrix[i][0] = 0

JavaScript Solution:

var setZeroes = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    let firstRowZero = false, firstColZero = false;
    for (let j = 0; j < n; j++) if (matrix[0][j] === 0) firstRowZero = true;
    for (let i = 0; i < m; i++) if (matrix[i][0] === 0) firstColZero = true;
    for (let i = 1; i < m; i++)
        for (let j = 1; j < n; j++)
            if (matrix[i][j] === 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
    for (let i = 1; i < m; i++)
        for (let j = 1; j < n; j++)
            if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
    if (firstRowZero) for (let j = 0; j < n; j++) matrix[0][j] = 0;
    if (firstColZero) for (let i = 0; i < m; i++) matrix[i][0] = 0;
};

Java Solution:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
        if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}