Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Input: [[1,1,1],[1,0,1],[1,1,1]] → Output: [[1,0,1],[0,0,0],[1,0,1]]Input: [[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. Scan matrix for zeros, mark their row and column in first row/col. Then zero out marked rows and columns.
- Track if first row/col themselves should be zeroed.
- Scan matrix[1..m][1..n]: if zero, mark matrix[0][j]=0 and matrix[i][0]=0.
- Zero out marked rows/cols from matrix[1..][1..].
- Apply first row/col zeroing if needed.
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[0][j]=0; matrix[i][0]=0; }
for (int i=1;i<m;i++) for (int j=1;j<n;j++) if (matrix[0][j]==0||matrix[i][0]==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;
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(1)