Set Matrix Zeroes

Given an m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Example

Text

Input:      Output:
1 0 1       0 0 0
1 1 1       1 0 1
1 0 1       0 0 0

The difficulty is that zeros you write must not trigger more zeroing. Zeroing row 0 as soon as you see (0, 1) would make it look as if every column had a zero.

Brute force: read from a copy

Scan an unchanged copy (each row is cloned, because copying only the outer array would share the rows) to find the original zeros, and write into the real matrix.

Java

import java.util.Arrays;

public class Main {
    static void setZeroes(int[][] matrix) {
        int[][] original = new int[matrix.length][];
        for (int i = 0; i < matrix.length; i++) original[i] = matrix[i].clone();
        for (int i = 0; i < original.length; i++) {
            for (int j = 0; j < original[i].length; j++) {
                if (original[i][j] == 0) {
                    Arrays.fill(matrix[i], 0);
                    for (int[] row : matrix) row[j] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] m = {{1, 0, 1}, {1, 1, 1}, {1, 0, 1}};
        setZeroes(m);
        System.out.println(Arrays.deepToString(m));
    }
}

Output

[[0, 0, 0], [1, 0, 1], [0, 0, 0]]

Time: O(m·n·(m + n)): every zero clears a row and a column. Space: O(m·n) for the copy.

Recording which rows and which columns contain a zero in two boolean arrays (O(m + n) space) and clearing each marked row and column once brings the time down to O(m·n).

Optimal: use the first row and column as markers

The two marker arrays can live inside the matrix itself: matrix[i][0] = 0 marks row i, and matrix[0][j] = 0 marks column j. Cell (0, 0) would have to serve both row 0 and column 0, so row 0's own flag is kept in a separate variable.

Remember whether row 0 contains a zero.
For every zero at (i, j) below row 0, mark matrix[i][0] and matrix[0][j].
Zero every cell below row 0 whose row or column is marked.
If column 0 is marked, zero column 0. If row 0 had a zero, zero row 0. These go last so the markers are read before they're overwritten.

Java

import java.util.Arrays;

public class Main {
    static void setZeroes(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        boolean firstRowZero = false;
        for (int x : matrix[0]) {
            if (x == 0) firstRowZero = true;
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (matrix[0][0] == 0) {
            for (int[] row : matrix) row[0] = 0;
        }
        if (firstRowZero) Arrays.fill(matrix[0], 0);
    }

    public static void main(String[] args) {
        int[][] m = {{1, 0, 1}, {1, 1, 1}, {1, 0, 1}};
        setZeroes(m);
        System.out.println(Arrays.deepToString(m));

        m = new int[][]{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(m);
        System.out.println(Arrays.deepToString(m));
    }
}

Output

[[0, 0, 0], [1, 0, 1], [0, 0, 0]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

Time: O(m·n). Space: O(1).

matrix[0][0] ends up 0 if column 0 had a zero anywhere below row 0 (step 2), or if matrix[0][0] was 0 to begin with. In both cases column 0 must be cleared.

Edge cases

No zeros: nothing changes.
Zero in the first row or column only: handled by firstRowZero and the matrix[0][0] check.
Single row or column: the loops that start at 1 do nothing, and the final steps handle it.