Set Matrix Zeroes

For every 0 found in a matrix, zero out its entire row and column. (LeetCode 73)

Brute force: naively zeroing in-place as you scan causes cascading false zeros (a zero created by an earlier zero’s row/column triggers more zeroing). Fix by marking cells for zeroing with a sentinel (e.g. -1) during the first pass, then converting all -1s to 0 in a second pass.

Better — two marker arrays: a row[] of size n and col[] of size m, initialized to 0. On finding arr[i][j] == 0, set row[i] = 1 and col[j] = 1. Then a second pass zeroes any cell where its row or column is marked.

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] row = new int[n];
        int[] col = new int[m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == 0){
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(row[i] == 1 || col[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Time: O(n×m). Space: O(n+m).

Optimal: fold the row[]/col[] marker arrays into the matrix itself — use the matrix’s own first row and first column as the marker arrays (with a separate flag to handle the cell where they’d overlap), eliminating the extra O(n+m) space.