If element is 0, set its entire row and column to 0. Do it in place.
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]]
Use first row and first column as markers. Handle them separately.
- Check if first row/col contains zero
- Mark zeros using first row (for columns) and first col (for rows)
- Process rest of matrix using markers
- Zero out marked rows and columns
- Handle first row/col at end
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRow = false, firstCol = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = 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 (firstRow) Arrays.fill(matrix[0], 0);
if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
- Time Complexity: O(m*n)
- Space Complexity: O(1)