Set Matrix Zeroes

Share

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

Example 1
Input: [[1,1,1],[1,0,1],[1,1,1]] → Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2
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]]

Solution Approach

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.
Java
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)