70. Set Matrix Zeroes

Use the matrix's own first row and first column as bookmarks: when cell (i,j) is 0, record it by zeroing matrix[i][0] and matrix[0][j]. Two boolean flags remember whether the first row/column themselves need zeroing, so no extra space is used.

Idea

The naive approach uses O(m+n) extra memory to remember which rows and columns to zero. We can drop that to O(1) by storing the markers inside the matrix itself — in the first row and first column.

The only complication: the first row and first column can't record their own state without ambiguity, so we handle them with two separate boolean flags first.

Algorithm

1. first_row_zero = does row 0 contain a 0? first_col_zero = does column 0 contain a 0?
2. For every inner cell (i,j) with i,j >= 1: if it's 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
3. For every inner cell (i,j): if its row-marker matrix[i][0] or column-marker matrix[0][j] is 0, set matrix[i][j] = 0.
4. If first_row_zero, zero all of row 0. If first_col_zero, zero all of column 0.

Worked example: [[1,1,1],[1,0,1],[1,1,1]]

• Row 0 and column 0 have no zeros → both flags false.
• Inner scan: cell (1,1)=0 → set marker matrix[1][0]=0 and matrix[0][1]=0.
• Apply markers: row 1 (marker at (1,0)) and column 1 (marker at (0,1)) get zeroed → [[1,0,1],[0,0,0],[1,0,1]].
• Flags false, so first row/column keep their non-marker values.

Complexity

• Time: O(m·n).
• Space: O(1) — markers live in the matrix; only two boolean flags extra.

class Solution {
    public int[][] 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;
        return matrix;
    }
}