Set Matrix Zeroes

Share

If element is 0, set its entire row and column to 0. Do it in place.

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

Solution Approach

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