Set Matrix Zeroes | Leetcode

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

click to show follow up.

 

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

---

Solution: Use two booleans, one for first row, one for first column. Check if first row and first column is zero. Then check all other rows and columns to see if that row and column is zero. Mark all rows other than the first row. Mark all columns other than the first column. Mark the first row and first column as needed.

Algorithm 1: Use for loops

public class Solution {
    public void setZeroes(int[][] matrix) {
        int numRows = matrix.length;
        int numCols = matrix[0].length;
        boolean isFirstRowZero = false;
        boolean isFirstColZero = false;
        
        // Check if first row is zero.
        for (int col = 0; col < numCols; col++) {
            if (matrix[0][col] == 0) {
                isFirstRowZero = true;
                break;
            }
        }
        
        // Check if first column is zero.
        for (int row = 0; row < numRows; row++) {
            if (matrix[row][0] == 0) {
                isFirstColZero = true;
                break;
            }
        }
        
        // Check if each row/column is zero by marking zero in first column/row.
        for (int row = 1; row < numRows; row++) {
            for (int col = 1; col < numCols; col++) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }
        
        // Mark all rows except first.
        for (int row = 1; row < numRows; row++) {
            if (matrix[row][0] == 0) {
                for (int col = 1; col < numCols; col++) {
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Mark all columns except first.
        for (int col = 1; col < numCols; col++) {
            if (matrix[0][col] == 0) {
                for (int row = 1; row < numRows; row++) {
                    matrix[row][col] = 0;
                }
            }
        }

        // Mark first row.
        if (isFirstRowZero) {
            for (int col = 0; col < numCols; col++) {
                matrix[0][col] = 0;
            }
        }
        
        // Mark first column.
        if (isFirstColZero) {
            for (int row = 0; row < numRows; row++) {
                matrix[row][0] = 0;
            }
        }
    }
}

Algorithm 2: Use Java 8 streams

public class Solution {
    private int[][] matrix;
        
    public void setZeroes(int[][] matrix) {
        this.matrix = matrix;
        
        boolean isFirstRowZero = rowHasZero(0);
        boolean isFirstColZero = colHasZero(0);
        
        rows(1).filter(row -> rowHasZero(row)).forEach(row -> matrix[row][0] = 0);
        cols(1).filter(col -> colHasZero(col)).forEach(col -> matrix[0][col] = 0);
        
        rows(1).filter(row -> matrix[row][0] == 0).forEach(row -> setRowToZeros(row));
        cols(1).filter(col -> matrix[0][col] == 0).forEach(col -> setColToZeros(col));

        if (isFirstRowZero) setRowToZeros(0);
        if (isFirstColZero) setColToZeros(0);
    }
    
    private IntStream rows(int start) {
        return IntStream.range(start, matrix.length);
    }
    
    private IntStream cols(int start) {
        return IntStream.range(start, matrix[0].length);
    }
    
    private boolean rowHasZero(int row) {
        return cols(0).anyMatch(col -> matrix[row][col] == 0);
    }

    private boolean colHasZero(int col) {
        return rows(0).anyMatch(row -> matrix[row][col] == 0);
    }

    private void setRowToZeros(int row) {
        cols(0).forEach(col -> matrix[row][col] = 0);
    }
    
    private void setColToZeros(int col) {
        rows(0).forEach(row -> matrix[row][col] = 0);
    }
}