Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Set Matrix Zeroes

Sharing is caring!

Problem Statement
Given a m x n 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]
]
Solution
We will use the first cell of every row and column as a flag. This flag would determine whether a row or column should set to zero. These flags are used later to update the matrix. If the first cell of a row is set to zero this means the row should be marked zero. If the first cell of a column is set to zero this means the column should be marked zero. The first cell of row and column for the first row and first column is the same i.e. matrix[0][0]. Hence, we use additional variables to tell us if the first column and row had been marked.
class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean firstRow = false;
        boolean firstCol = false;
        
        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                    
                    if (r==0) {
                        firstRow = true;
                    }

                    if (c==0) {
                        firstCol = true;
                    }
                }
            
            }
        }
        
        for (int r=1; r<rows; r++) {
            for (int c=1; c<cols; c++) {
                if (matrix[r][0]==0) {
                    matrix[r][c] = 0;
                    
                }
                if (matrix[0][c]==0) {
                    matrix[r][c] = 0;
                }
            }
        }

        if (firstRow) {
            for (int c=0; c<cols; c++) {
                matrix[0][c] = 0;
            }
        }
        
        if (firstCol) {
            for (int r=0; r<rows; r++) {
                matrix[r][0] = 0;
            }
        }
    }
}